All reports by Author Wenceslas Fernandez de la Vega:

__
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

__
TR06-124
| 25th September 2006
__

Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski#### Approximation of Global MAX-CSP Problems

__
TR06-104
| 25th August 2006
__

Wenceslas Fernandez de la Vega, Marek Karpinski#### On the Sample Complexity of MAX-CUT

__
TR06-101
| 22nd August 2006
__

Wenceslas Fernandez de la Vega, Marek Karpinski#### Approximation Complexity of Nondense Instances of MAX-CUT

__
TR02-070
| 13th December 2002
__

Wenceslas Fernandez de la Vega, Marek Karpinski#### 9/8-Approximation Algorithm for Random MAX-3SAT

Revisions: 1

__
TR02-044
| 16th July 2002
__

Wenceslas Fernandez de la Vega, Marek Karpinski#### A Polynomial Time Approximation Scheme for Subdense MAX-CUT

__
TR02-041
| 2nd July 2002
__

Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon#### A Polynomial Time Approximation Scheme for Metric MIN-BISECTION

__
TR02-025
| 26th April 2002
__

Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani#### Polynomial Time Approximation Schemes for Metric Min-Sum Clustering

__
TR01-100
| 14th December 2001
__

Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski#### Random Sampling and Approximation of MAX-CSP Problems

__
TR01-034
| 30th April 2001
__

Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski#### Polynomial Time Approximation Schemes for Dense Instances of Minimum Constraint Satisfaction

__
TR00-091
| 21st December 2000
__

Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski#### Approximability of Dense Instances of NEAREST CODEWORD Problem

__
TR98-064
| 6th November 1998
__

Wenceslas Fernandez de la Vega, Marek Karpinski#### Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT

__
TR98-024
| 28th April 1998
__

Wenceslas Fernandez de la Vega, Marek Karpinski#### On Approximation Hardness of Dense TSP and other Path Problems

Wenceslas Fernandez de la Vega, Marek Karpinski

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 >>>

Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski

We study the problem of absolute approximability of MAX-CSP problems with the global constraints. We prove existence of an efficient sampling method for the MAX-CSP class of problems with linear global constraints and bounded feasibility gap. It gives for the first time a polynomial in epsilon^-1 sample complexity bound for ... more >>>

Wenceslas Fernandez de la Vega, Marek Karpinski

We give a simple proof for the sample complexity bound $O~(1/\epsilon^4)$ of absolute approximation of MAX-CUT. The proof depends on a new analysis method for linear programs (LPs) underlying MAX-CUT which could be also of independent interest.

more >>>Wenceslas Fernandez de la Vega, Marek Karpinski

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 >>>

Wenceslas Fernandez de la Vega, Marek Karpinski

We prove that MAX-3SAT can be approximated in polynomial time

within a factor 9/8 on random instances.

Wenceslas Fernandez de la Vega, Marek Karpinski

We prove that the subdense instances of MAX-CUT of average

degree Omega(n/logn) posses a polynomial time approximation scheme (PTAS).

We extend this result also to show that the instances of general 2-ary

maximum constraint satisfaction problems (MAX-CSP) of the same average

density have PTASs. Our results ...
more >>>

Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon

We design a polynomial time approximation scheme (PTAS) for

the problem of Metric MIN-BISECTION of dividing a given finite metric

space into two halves so as to minimize the sum of distances across

that partition. The method of solution depends on a new metric placement

partitioning ...
more >>>

Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani

We give polynomial time approximation schemes for the problem

of partitioning an input set of n points into a fixed number

k of clusters so as to minimize the sum over all clusters of

the total pairwise distances in a cluster. Our algorithms work

for arbitrary metric spaces as well ...
more >>>

Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski

We present a new efficient sampling method for approximating

r-dimensional Maximum Constraint Satisfaction Problems, MAX-rCSP, on

n variables up to an additive error \epsilon n^r.We prove a new

general paradigm in that it suffices, for a given set of constraints,

to pick a small uniformly random ...
more >>>

Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski

It is known that large fragments of the class of dense

Minimum Constraint Satisfaction (MIN-CSP) problems do not have

polynomial time approximation schemes (PTASs) contrary to their

Maximum Constraint Satisfaction analogs. In this paper we prove,

somewhat surprisingly, that the minimum satisfaction of dense

instances of kSAT-formulas, ...
more >>>

Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski

We give a polynomial time approximation scheme (PTAS) for dense

instances of the NEAREST CODEWORD problem.

Wenceslas Fernandez de la Vega, Marek Karpinski

We give the first polynomial time approximability characterization

of dense weighted instances of MAX-CUT, and some other dense

weighted NP-hard problems in terms of their empirical weight

distributions. This gives also the first almost sharp

characterization of inapproximability of unweighted 0,1

MAX-BISECTION instances ...
more >>>

Wenceslas Fernandez de la Vega, Marek Karpinski

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 >>>