Robust optimization of graph partitioning involving interval uncertainty

Neng Fan; Qipeng P. Zheng; Panos M. Pardalos

doi:10.1016/j.tcs.2011.10.015

Robust optimization of graph partitioning involving interval uncertainty

Neng Fan, Qipeng P. Zheng, Panos M. Pardalos

Research output: Contribution to journal › Article › peer-review

14 Scopus citations

Abstract

The graph partitioning problem consists of partitioning the vertex set of a graph into several disjoint subsets so that the sum of weights of the edges between the disjoint subsets is minimized. In this paper, robust optimization models with two decomposition algorithms are introduced to solve the graph partitioning problem with interval uncertain weights of edges. The bipartite graph partitioning problem with edge uncertainty is also presented. Throughout this paper, we make no assumption regarding the probability of the uncertain weights.

Original language	English (US)
Pages (from-to)	53-61
Number of pages	9
Journal	Theoretical Computer Science
Volume	447
DOIs	https://doi.org/10.1016/j.tcs.2011.10.015
State	Published - Aug 17 2012
Externally published	Yes

Keywords

Benders decomposition
Bipartite graph partitioning
Graph partitioning
Robust optimization
Uncertainty

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1016/j.tcs.2011.10.015

Cite this

@article{591b642098244cdf91c75367802e742f,

title = "Robust optimization of graph partitioning involving interval uncertainty",

abstract = "The graph partitioning problem consists of partitioning the vertex set of a graph into several disjoint subsets so that the sum of weights of the edges between the disjoint subsets is minimized. In this paper, robust optimization models with two decomposition algorithms are introduced to solve the graph partitioning problem with interval uncertain weights of edges. The bipartite graph partitioning problem with edge uncertainty is also presented. Throughout this paper, we make no assumption regarding the probability of the uncertain weights.",

keywords = "Benders decomposition, Bipartite graph partitioning, Graph partitioning, Robust optimization, Uncertainty",

author = "Neng Fan and Zheng, {Qipeng P.} and Pardalos, {Panos M.}",

year = "2012",

month = aug,

day = "17",

doi = "10.1016/j.tcs.2011.10.015",

language = "English (US)",

volume = "447",

pages = "53--61",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Robust optimization of graph partitioning involving interval uncertainty

AU - Fan, Neng

AU - Zheng, Qipeng P.

AU - Pardalos, Panos M.

PY - 2012/8/17

Y1 - 2012/8/17

N2 - The graph partitioning problem consists of partitioning the vertex set of a graph into several disjoint subsets so that the sum of weights of the edges between the disjoint subsets is minimized. In this paper, robust optimization models with two decomposition algorithms are introduced to solve the graph partitioning problem with interval uncertain weights of edges. The bipartite graph partitioning problem with edge uncertainty is also presented. Throughout this paper, we make no assumption regarding the probability of the uncertain weights.

AB - The graph partitioning problem consists of partitioning the vertex set of a graph into several disjoint subsets so that the sum of weights of the edges between the disjoint subsets is minimized. In this paper, robust optimization models with two decomposition algorithms are introduced to solve the graph partitioning problem with interval uncertain weights of edges. The bipartite graph partitioning problem with edge uncertainty is also presented. Throughout this paper, we make no assumption regarding the probability of the uncertain weights.

KW - Benders decomposition

KW - Bipartite graph partitioning

KW - Graph partitioning

KW - Robust optimization

KW - Uncertainty

UR - http://www.scopus.com/inward/record.url?scp=84863320034&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84863320034&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2011.10.015

DO - 10.1016/j.tcs.2011.10.015

M3 - Article

AN - SCOPUS:84863320034

SN - 0304-3975

VL - 447

SP - 53

EP - 61

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Robust optimization of graph partitioning involving interval uncertainty

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this