Interdicting structured combinatorial optimization problems with {0,1}-objectives

DOI10.1287/MOOR.2016.0798MaRDI QIDQ2976146zbMATH OpenOpenAlexFDO

Authors Rico Zenklusen, Stephen R. Chestnut

Publication date 13 April 2017

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.02484

zbMATH Keywords

approximation algorithmsinterdictionmatroidsrobustness

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Combinatorial optimization (90C27) Multi-objective and goal programming (90C29)

Abstract: Interdiction problems ask about the worst-case impact of a limited change to an underlying optimization problem. They are a natural way to measure the robustness of a system, or to identify its weakest spots. Interdiction problems have been studied for a wide variety of classical combinatorial optimization problems, including maximum $s$-$t$ flows, shortest $s$-$t$ paths, maximum weight matchings, minimum spanning trees, maximum stable sets, and graph connectivity. Most interdiction problems are NP-hard, and furthermore, even designing efficient approximation algorithms that allow for estimating the order of magnitude of a worst-case impact, has turned out to be very difficult. Not very surprisingly, the few known approximation algorithms are heavily tailored for specific problems. Inspired by an approach of Burch et al. (2003), we suggest a general method to obtain pseudoapproximations for many interdiction problems. More precisely, for any $alpha>0$, our algorithm will return either a $(1+alpha)$-approximation, or a solution that may overrun the interdiction budget by a factor of at most $1+alph{a}^{-1}$ but is also at least as good as the optimal solution that respects the budget. Furthermore, our approach can handle submodular interdiction costs when the underlying problem is to find a maximum weight independent set in a matroid, as for example the maximum weight forest problem. The approach can sometimes be refined by exploiting additional structural properties of the underlying optimization problem to obtain stronger results. We demonstrate this by presenting a PTAS for interdicting $b$-stable sets in bipartite graphs.

Recommendations

• Hardness and approximation for network flow interdiction
• Matching interdiction
• An approximation algorithm for network flow interdiction with unit costs and two capacities
• Interdiction problems on planar graphs
• Packing interdiction and partial covering problems

Cites work

• Budgeted Matching and Budgeted Matroid Intersection Via the Gasoline Puzzle
• Combinatorial Optimization with Rational Objective Functions
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Complexity of determining the most vital elements for the p-median and p-center location problems
• Computing Maximal “Polymatroidal” Network Flows
• Connectivity interdiction
• Deterministic network interdiction
• Extended formulations in combinatorial optimization
• Finding the most vital arcs in a network
• Hardness and approximation for network flow interdiction
• scientific article; zbMATH DE number 6515828 (Why is no real title available?)
• scientific article; zbMATH DE number 1302174 (Why is no real title available?)
• scientific article; zbMATH DE number 2050720 (Why is no real title available?)
• scientific article; zbMATH DE number 2050722 (Why is no real title available?)
• scientific article; zbMATH DE number 871953 (Why is no real title available?)
• scientific article; zbMATH DE number 6472643 (Why is no real title available?)
• Interdiction problems on planar graphs
• Matching interdiction
• Network flow interdiction on planar graphs
• New approaches to multi-objective optimization
• On Budgeted Optimization Problems
• On short paths interdiction problems: Total and node-wise limited interdiction
• On the diameter of the edge cover polytope
• On the history of the transportation and maximum flow problems
• Packing interdiction and partial covering problems
• Relations between average case complexity and approximation complexity
• Removing Arcs from a Network
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• The most vital nodes with respect to independent set and vertex cover
• The network inhibition problem

Cited in

(16)

• On the hardness of covering-interdiction problems
• An approximation algorithm for network flow interdiction with unit costs and two capacities
• Interdicting facilities in tree networks
• Bulk-robust combinatorial optimization
• Matrix interdiction problem
• scientific article; zbMATH DE number 2050722 (Why is no real title available?)
• Packing interdiction and partial covering problems
• Symmetric interdiction for matching problems
• On the independent set interdiction problem
• Integer Programming Formulations for Minimum Spanning Tree Interdiction
• Vertex downgrading to minimize connectivity
• Parametric matroid interdiction
• Approximation algorithms for two extensions of min-k-union
• On extensions of min-k-union
• The parametric matroid -interdiction problem
• Interdiction of minimum spanning trees and other matroid bases

This page was built for publication: Interdicting structured combinatorial optimization problems with {0,1}-objectives

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