z-Approximations

Refael Hassin*, Samir Khuller

*Corresponding author for this work

Research output: Contribution to journalArticle

44 Scopus citations

Abstract

Approximation algorithms for NP-hard optimization problems have been widely studied for over three decades. Most of these measure the quality of the solution produced by taking the ratio of the cost of the solution produced by the algorithm to the cost of an optimal solution. In certain cases, this ratio may not be very meaningful - for example, if the ratio of the worst solution to the best solution is at most some constant α, then an approximation algorithm with factor α may in fact yield the worst solution! To overcome this hurdle (among others), several authors have independently suggested the use of a different measure which we call z-approximation. An algorithm is an α z-approximation if it runs in polynomial time and produces a solution whose distance from the optimal one is at most α times the distance between the optimal solution and the worst possible solution. The results known so far about z-approximations are either of the inapproximability type or rather straightforward observations. We design polynomial time algorithms for several fundamental discrete optimization problems; in particular we obtain a z-approximation factor of 1/2 for the DIRECTED TRAVELING SALESMAN PROBLEM (TSP) (with no triangle inequality assumption). For the UNDIRECTED TSP this improves to 1/3. We also show that if there is a polynomial time algorithm that for any fixed ∈ > 0 yields an ∈ z-approximation then P = NP. We also present z-approximations for several other problems such as MAX CUT, STACKER CRANE, MAXIMUM ACYCLIC SUBGRAPH, and MINIMUM DISJOINT CYCLE COVER.

Original languageEnglish (US)
Pages (from-to)429-442
Number of pages14
JournalJournal of Algorithms
Volume41
Issue number2
DOIs
StatePublished - Jan 1 2001

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'z-Approximations'. Together they form a unique fingerprint.

  • Cite this