Complexity of the min-max (regret) versions of min cut problems
From MaRDI portal
Publication:924631
DOI10.1016/j.disopt.2007.11.008zbMath1134.90048OpenAlexW2068827145MaRDI QIDQ924631
Daniel Vanderpooten, Hassene Aissi, Cristina Bazgan
Publication date: 16 May 2008
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disopt.2007.11.008
Related Items (7)
A new bound for the midpoint solution in minmax regret optimization with an application to the robust shortest path problem ⋮ Robust Algorithms for TSP and Steiner Tree ⋮ Using the WOWA operator in robust discrete optimization problems ⋮ A note on the nonexistence of oracle-polynomial algorithms for robust combinatorial optimization ⋮ Exact and heuristic algorithms for the interval data robust assignment problem ⋮ Combinatorial optimization problems with uncertain costs and the OWA criterion ⋮ Combinatorial two-stage minmax regret problems under interval uncertainty
Cites Work
- Complexity of the min-max and min-max regret assignment problems
- Approximation of min-max and min-max regret versions of some combinatorial optimization problems
- An approximation algorithm for interval data minmax regret combinatorial optimization problems
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- Robust discrete optimization and its applications
- On the complexity of the robust spanning tree problem with interval data
- Interval data minmax regret network optimization problems
- Multicriteria global minimum cuts
- A new approach to the minimum cut problem
- Computing All Small Cuts in an Undirected Network
- A simple min-cut algorithm
- The robust spanning tree problem with interval data
- Unnamed Item
- Unnamed Item
This page was built for publication: Complexity of the min-max (regret) versions of min cut problems
