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

Klaus Jansen, Marek Karpinski, Andrzej Lingas

The Max-Bisection and Min-Bisection are the problems of finding

partitions of the vertices of a given graph into two equal size subsets so as

to maximize or minimize, respectively, the number of edges with exactly one

endpoint in each subset.

In this paper we design the first ...
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.

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

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

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

Marek Karpinski

We survey some recent results on the complexity of computing

approximate solutions for instances of the Minimum Bisection problem

and formulate some intriguing and still open questions about the

approximability status of that problem. Some connections to other

optimization problems are also indicated.