TY - GEN

T1 - Algorithms for inverse optimization problems

AU - Ahmadian, Sara

AU - Bhaskar, Umang

AU - Sanità, Laura

AU - Swamy, Chaitanya

PY - 2018/8/1

Y1 - 2018/8/1

N2 - We study inverse optimization problems, wherein the goal is to map given solutions to an underlying optimization problem to a cost vector for which the given solutions are the (unique) optimal solutions. Inverse optimization problems find diverse applications and have been widely studied. A prominent problem in this field is the inverse shortest path (ISP) problem [9, 3, 4], which finds applications in shortest-path routing protocols used in telecommunications. Here we seek a cost vector that is positive, integral, induces a set of given paths as the unique shortest paths, and has minimum ℓ∞ norm. Despite being extensively studied, very few algorithmic results are known for inverse optimization problems involving integrality constraints on the desired cost vector whose norm has to be minimized. Motivated by ISP, we initiate a systematic study of such integral inverse optimization problems from the perspective of designing polynomial time approximation algorithms. For ISP, our main result is an additive 1-approximation algorithm for multicommodity ISP with node-disjoint commodities, which we show is tight assuming P ≠ NP. We then consider the integral-cost inverse versions of various other fundamental combinatorial optimization problems, including min-cost flow, max/min-cost bipartite matching, and max/min-cost basis in a matroid, and obtain tight or nearly-tight approximation guarantees for these. Our guarantees for the first two problems are based on results for a broad generalization, namely integral inverse polyhedral optimization, for which we also give approximation guarantees. Our techniques also give similar results for variants, including ℓp-norm minimization of the integral cost vector, and distance-minimization from an initial cost vector.

AB - We study inverse optimization problems, wherein the goal is to map given solutions to an underlying optimization problem to a cost vector for which the given solutions are the (unique) optimal solutions. Inverse optimization problems find diverse applications and have been widely studied. A prominent problem in this field is the inverse shortest path (ISP) problem [9, 3, 4], which finds applications in shortest-path routing protocols used in telecommunications. Here we seek a cost vector that is positive, integral, induces a set of given paths as the unique shortest paths, and has minimum ℓ∞ norm. Despite being extensively studied, very few algorithmic results are known for inverse optimization problems involving integrality constraints on the desired cost vector whose norm has to be minimized. Motivated by ISP, we initiate a systematic study of such integral inverse optimization problems from the perspective of designing polynomial time approximation algorithms. For ISP, our main result is an additive 1-approximation algorithm for multicommodity ISP with node-disjoint commodities, which we show is tight assuming P ≠ NP. We then consider the integral-cost inverse versions of various other fundamental combinatorial optimization problems, including min-cost flow, max/min-cost bipartite matching, and max/min-cost basis in a matroid, and obtain tight or nearly-tight approximation guarantees for these. Our guarantees for the first two problems are based on results for a broad generalization, namely integral inverse polyhedral optimization, for which we also give approximation guarantees. Our techniques also give similar results for variants, including ℓp-norm minimization of the integral cost vector, and distance-minimization from an initial cost vector.

KW - Approximation algorithms

KW - Combinatorial optimization

KW - Inverse optimization

KW - Linear programming

KW - Polyhedral theory

KW - Shortest paths

UR - http://www.scopus.com/inward/record.url?scp=85052527302&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ESA.2018.1

DO - 10.4230/LIPIcs.ESA.2018.1

M3 - Conference contribution

AN - SCOPUS:85052527302

SN - 9783959770811

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 26th European Symposium on Algorithms, ESA 2018

A2 - Bast, Hannah

A2 - Herman, Grzegorz

A2 - Azar, Yossi

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 26th European Symposium on Algorithms, ESA 2018

Y2 - 20 August 2018 through 22 August 2018

ER -