Robust optimization of graph partitioning involving interval uncertainty

DOI10.1016/j.tcs.2011.10.015zbMath1245.05101OpenAlexW2045321028WikidataQ57734132 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

uncertaintygraph partitioningrobust optimizationBenders decompositionbipartite graph partitioning

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

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