A Theory and Algorithms for Combinatorial Reoptimization

Baruch Schieber, Hadas Shachnai, Gal Tamir, Tami Tamir

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

Many real-life applications involve systems that change dynamically over time. Thus, throughout the continuous operation of such a system, it is required to compute solutions for new problem instances, derived from previous instances. Since the transition from one solution to another incurs some cost, a natural goal is to have the solution for the new instance close to the original one (under a certain distance measure). In this paper we develop a general framework for combinatorial repotimization, encompassing classical objective functions as well as the goal of minimizing the transition cost from one solution to the other. Formally, we say that A is an (r, ρ) -reapproximation algorithm if it achieves a ρ-approximation for the optimization problem, while paying a transition cost that is at most r times the minimum required for solving the problem optimally. Using our model we derive reoptimization and reapproximation algorithms for several classes of combinatorial reoptimization problems. This includes a fully polynomial time (1 + ε1, 1 + ε2) -reapproximation scheme for the wide class of DP-benevolent problems introduced by Woeginger (Proceedings of Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999), a (1, 3)-reapproximation algorithm for the metric k-Center problem, and (1, 1)-reoptimization algorithm for polynomially solvable subset-selection problems. Thus, we distinguish here for the first time between classes of reoptimization problems by their hardness status with respect to the objective of minimizing transition costs, while guaranteeing a good approximation for the underlying optimization problem.

Original languageEnglish (US)
Pages (from-to)576-607
Number of pages32
JournalAlgorithmica
Volume80
Issue number2
DOIs
StatePublished - Feb 1 2018
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Keywords

  • Approximation schemes
  • Combinatorial reoptimization
  • Reapproximation
  • Subset selection
  • k-Center

Fingerprint

Dive into the research topics of 'A Theory and Algorithms for Combinatorial Reoptimization'. Together they form a unique fingerprint.

Cite this