Robust optimization of graph partitioning involving interval uncertainty

DOI10.1016/j.tcs.2011.10.015zbMath1245.05101WikidataQ57734132 ScholiaQ57734132MaRDI QIDQ443713

Panos M. Pardalos, Neng Fan, Qipeng Phil Zheng

Publication date: 13 August 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.10.015

zbMATH Keywords

uncertainty; graph partitioning; robust optimization; Benders decomposition; bipartite graph partitioning

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp>, Graph clustering with Boltzmann machines, An extended edge-representative formulation for the \(K\)-partitioning problem, A robust optimization approach for multicast network coding under uncertain link costs, Decomposition-based exact algorithms for risk-constrained traveling salesman problems with discrete random arc costs, An optimization-based approach for the healthcare districting under uncertainty, Robust Critical Node Selection by Benders Decomposition

Uses Software

• CPLEX

Cites Work

• Unnamed Item
• Multi-way clustering and biclustering by the ratio cut and normalized cut in graphs
• Some simplified NP-complete graph problems
• Multiset graph partitioning
• Graph partitioning using linear and semidefinite programming
• Robust discrete optimization and network flows
• An exact algorithm for the robust shortest path problem with interval data
• Global optimization in action. Continuous and Lipschitz optimization: algorithms, implementations and applications
• Linear and quadratic programming approaches for the general graph partitioning problem
• Semidefinite programming relaxations for the graph partitioning problem
• Robust Optimization of Graph Partitioning and Critical Node Detection in Analyzing Networks
• The Price of Robustness
• Technical Note—Convex Programming with Set-Inclusive Constraints and Applications to Inexact Linear Programming
• The robust spanning tree problem with interval data