Marek Karpinski

We survey recent results on the existence of polynomial time

approximation schemes for some dense instances of NP-hard

optimization problems. We indicate further some inherent limits

for existence of such schemes for some other dense instances of

the optimization problems.

Uriel Feige, Marek Karpinski, Michael Langberg

We analyze the addition of a simple local improvement step to various known

randomized approximation algorithms.

Let $\alpha \simeq 0.87856$ denote the best approximation ratio currently

known for the Max Cut problem on general graphs~\cite{GW95}.

We consider a semidefinite relaxation of the Max Cut problem,

round it using the ...
more >>>

Uriel Feige, Marek Karpinski, Michael Langberg

We design a $0.795$ approximation algorithm for the Max-Bisection problem

restricted to regular graphs. In the case of three regular graphs our

results imply an approximation ratio of $0.834$.

Marek Karpinski, Miroslaw Kowaluk, Andrzej Lingas

The max-bisection problem is to find a partition of the vertices of a

graph into two equal size subsets that maximizes the number of edges with

endpoints in both subsets.

We obtain new improved approximation ratios for the max-bisection problem on

the low degree $k$-regular graphs for ...
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 >>>

Lars Engebretsen, Marek Karpinski

The general asymmetric (and metric) TSP is known to be approximable

only to within an O(log n) factor, and is also known to be

approximable within a constant factor as soon as the metric is

bounded. In this paper we study the asymmetric and symmetric TSP

problems with bounded metrics ...
more >>>

Piotr Berman, Marek Karpinski

We consider bounded occurrence (degree) instances of a minimum

constraint satisfaction problem MIN-LIN2 and a MIN-BISECTION problem for

graphs. MIN-LIN2 is an optimization problem for a given system of linear

equations mod 2 to construct a solution that satisfies the minimum number

of them. E3-OCC-MIN-E3-LIN2 ...
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 >>>

Marek Karpinski

We present some of the recent results on computational complexity

of approximating bounded degree combinatorial optimization problems. In

particular, we present the best up to now known explicit nonapproximability

bounds on the very small degree optimization problems which are of

particular importance on the intermediate stages ...
more >>>

Piotr Berman, Sridhar Hannenhalli, Marek Karpinski

Analysis of genomes evolving by inversions leads to a general

combinatorial problem of {\em Sorting by Reversals}, MIN-SBR, the problem of

sorting a permutation by a minimum number of reversals.

This combinatorial problem has a long history, and a number of other

motivations. It was studied in a great ...
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 >>>

Piotr Berman, Marek Karpinski

We prove that the problems of minimum bisection on k-uniform

hypergraphs are almost exactly as hard to approximate,

up to the factor k/3, as the problem of minimum bisection

on graphs. On a positive side, our argument gives also the

first approximation ...
more >>>