✦ LIBER ✦

On the efficiency of polynomial time approximation schemes

✍ Scribed by Marco Cesati; Luca Trevisan

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 630 KB
Volume: 64
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(97)00164-6

No coin nor oath required. For personal study only.

✦ Synopsis

A polynomial time approximation scheme (PTAS) for an optimization problem A is an algorithm that given in input an instance of A and E > 0 find;,; (1 + E)-approximate solution in time that is polynomial for each fixed E. Typical running times are no(+) or 2"' n. While algorithms of the former kind tend to be impractical, the latter ones are more interesting. In several cases, the development of algorithms of the second type required considerably new, and sometimes harder, techniques. For some interesting problems, only n"("E) approximation schemes are known. Under likely assumptions, we prove that for some problems (including natural ones) there cannot be approximation schemes running in time f( l/n)nO('), no matter how fast function f grows. Our result relies on a connection with Parameterized Complexity Theory, and we show that this connection is necessary. @

📜 SIMILAR VOLUMES

Polynomial time approximation schemes fo

Polynomial time approximation schemes for class-constrained packing problems

✍ Hadas Shachnai; Tami Tamir 📂 Article 📅 2001 🏛 Springer US 🌐 English ⚖ 207 KB

We consider variants of the classic bin packing and multiple knapsack problems, in which sets of items of di erent classes (colours) need to be placed in bins; the items may have di erent sizes and values. Each bin has a limited capacity, and a bound on the number of distinct classes of items it can

Polynomial Time Approximation Schemes fo

Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems

✍ Sanjeev Arora; David Karger; Marek Karpinski 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 250 KB

We present a unified framework for designing polynomial time approximation schemes (PTASs) for ``dense'' instances of many NP-hard optimization problems, including maximum cut, graph bisection, graph separation, minimum k-way cut with and without specified terminals, and maximum 3-satisfiability. By

An efficient, strongly polynomial, ε-app

An efficient, strongly polynomial, ε-approximation parametric optimization scheme

✍ S.N. Kabadi; Y.P. Aneja 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 379 KB

Given a set X 5 Z", vectors c, d E IK", an interval [a, b] C R, a fixed 0 < E < 1, and an oracle that, for any 0 < E < 1 finds an E-approximate solution to problem max{hTx 1 x E X} for any h E RU", we present a theoretically and practically efficient e-approximation algorithm, for the problem min{u(

An efficient fully polynomial approximat

An efficient fully polynomial approximation scheme for the Subset-Sum Problem

✍ Hans Kellerer; Renata Mansini; Ulrich Pferschy; Maria Grazia Speranza 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 238 KB

Given a set of n positive integers and a knapsack of capacity c; the Subset-Sum Problem is to find a subset the sum of which is closest to c without exceeding the value c: In this paper we present a fully polynomial approximation scheme which solves the Subset-Sum Problem with accuracy e in time Oðm

A polynomial time approximation scheme f

A polynomial time approximation scheme for the SONET ring loading problem

✍ Sanjeev Khanna 📂 Article 📅 2002 🏛 Institute of Electrical and Electronics Engineers 🌐 English ⚖ 110 KB 👁 1 views

An asymptotic fully polynomial time appr

An asymptotic fully polynomial time approximation scheme for bin covering

✍ Klaus Jansen; Roberto Solis-Oba 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 175 KB

In the bin covering problem there is a group L = (a1; : : : ; an) of items with sizes s(ai) ∈ (0; 1), and the goal is to ÿnd a packing of the items into bins to maximize the number of bins that receive items of total size at least 1. This is a dual problem to the classical bin packing problem. In th