Robust optimization of graph partitioning involving interval uncertainty

DOI10.1016/J.TCS.2011.10.015MaRDI QIDQ443713zbMATH OpenOpenAlexWikidataFDO

Authors Neng Fan, Panos M. Pardalos, Qipeng P. 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

Benders decompositionbipartite graph partitioninggraph partitioningrobust optimizationuncertainty

Mathematics Subject Classification ID

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

Recommendations

• Robust optimization of graph partitioning and critical node detection in analyzing networks
• Interval-parameter optimization problems on graphs
• On the two-stage stochastic graph partitioning problem
• Robust maximum weighted independent-set problems on interval graphs
• Short paper -- A note on robust combinatorial optimization with generalized interval uncertainty

Cites work

• An exact algorithm for the robust shortest path problem with interval data
• Global optimization in action. Continuous and Lipschitz optimization: algorithms, implementations and applications
• Graph partitioning using linear and semidefinite programming
• scientific article; zbMATH DE number 1182569 (Why is no real title available?)
• Linear and quadratic programming approaches for the general graph partitioning problem
• Multi-way clustering and biclustering by the ratio cut and normalized cut in graphs
• Multiset graph partitioning
• Robust discrete optimization and network flows
• Robust optimization of graph partitioning and critical node detection in analyzing networks
• Semidefinite programming relaxations for the graph partitioning problem
• Some simplified NP-complete graph problems
• Technical Note—Convex Programming with Set-Inclusive Constraints and Applications to Inexact Linear Programming
• The Price of Robustness
• The robust spanning tree problem with interval data

Cited in

(9)

• An optimization-based approach for the healthcare districting under uncertainty
• Robust critical node selection by Benders decomposition
• Robust optimization of graph partitioning and critical node detection in analyzing networks
• An extended edge-representative formulation for the \(K\)-partitioning problem
• On the two-stage stochastic graph partitioning problem
• A robust optimization approach for multicast network coding under uncertain link costs
• The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp>
• Graph clustering with Boltzmann machines
• Decomposition-based exact algorithms for risk-constrained traveling salesman problems with discrete random arc costs

Describes a project that uses

Uses Software

• CPLEX

This page was built for publication: Robust optimization of graph partitioning involving interval uncertainty

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q443713)