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

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

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

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

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

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 display for the first ... more >>>

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 method which could be ... more >>>

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

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 subset of its variables, ... more >>>

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, and linear equations ... more >>>

We give a polynomial time approximation scheme (PTAS) for dense instances of the NEAREST CODEWORD problem. more >>>

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 in terms of their density parameter. more >>>

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 $0more >>>