Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Approximation Schemes:
TR96-043 | 16th August 1996
Edmund Ihler

On polynomial time approximation schemes and approximation preserving reductions

We show that a fully polynomial time approximation scheme given
for an optimization problem can always be simply modified to a
polynomial time algorithm solving the problem optimally if the
computation model is the deterministic Turing Machine or the
logarithmic cost RAM and ... more >>>

TR98-024 | 28th April 1998
Wenceslas Fernandez de la Vega, Marek Karpinski

On Approximation Hardness of Dense TSP and other Path Problems

TSP(1,2), the Traveling Salesman Problem with distances 1 and 2, is
the problem of finding a tour of minimum length in a complete
weighted graph where each edge has length 1 or 2. Let $d_o$ satisfy
$0<d_o<1/2$. We show that TSP(1,2) has no PTAS on the set ... more >>>

TR01-065 | 10th August 2001
Chandra Chekuri, Sanjeev Khanna

Approximation Schemes for Preemptive Weighted Flow Time

We present the first approximation schemes for minimizing weighted flow time
on a single machine with preemption. Our first result is an algorithm that
computes a $(1+\eps)$-approximate solution for any instance of weighted flow
time in $O(n^{O(\ln W \ln P/\eps^3)})$ time; here $P$ is the ratio ... more >>>

TR02-070 | 13th December 2002
Wenceslas Fernandez de la Vega, Marek Karpinski

9/8-Approximation Algorithm for Random MAX-3SAT

Revisions: 1

We prove that MAX-3SAT can be approximated in polynomial time
within a factor 9/8 on random instances.

more >>>

TR06-101 | 22nd August 2006
Wenceslas Fernandez de la Vega, Marek Karpinski

Approximation Complexity of Nondense Instances of MAX-CUT

We prove existence of approximation schemes for instances of MAX-CUT with $\Omega(\frac{n^2}{\Delta})$ edges which work in $2^{O^\thicksim(\frac{\Delta}{\varepsilon^2})}n^{O(1)}$ time. This entails in particular existence of quasi-polynomial approximation schemes (QPTASs) for mildly sparse instances of MAX-CUT with $\Omega(\frac{n^2}{\operatorname{polylog} n})$ edges. The result depends on new sampling method for smoothed linear programs that ... more >>>

TR06-144 | 21st November 2006
Claire Kenyon-Mathieu, Warren Schudy

How to rank with few errors: A PTAS for Weighted Feedback Arc Set on Tournaments

Suppose you ran a chess tournament, everybody played everybody, and you wanted to use the results to rank everybody. Unless you were really lucky, the results would not be acyclic, so you could not just sort the players by who beat whom. A natural objective is to find a ranking ... more >>>

TR06-155 | 15th December 2006
Wenceslas Fernandez de la Vega, Marek Karpinski

Trading Tensors for Cloning: Constant Time Approximation Schemes for Metric MAX-CSP

Revisions: 1

We construct the first constant time value approximation schemes (CTASs) for Metric and Quasi-Metric MAX-rCSP problems for any $r \ge 2$ in a preprocessed metric model of computation, improving over the previous results of [FKKV05] proven for the general core-dense MAX-rCSP problems. They entail also the first sublinear approximation schemes ... more >>>

ISSN 1433-8092 | Imprint