Marek Karpinski, Juergen Wirtgen

The bandwidth problem is the problem of enumerating

the vertices of a given graph $G$ such that the maximum

difference between the numbers of

adjacent vertices is minimal. The problem has a long

history and a number of applications

and is ...
more >>>

Gunter Blache, Marek Karpinski, Juergen Wirtgen

The bandwidth problem is the problem of enumerating

the vertices of a given graph $G$ such that the maximum difference

between the numbers of adjacent vertices is minimal. The problem

has a long history and a number of applications.

There was not ...
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 >>>

Piotr Berman, Marek Karpinski

We prove a number of improved inaproximability results,

including the best up to date explicit approximation

thresholds for MIS problem of bounded degree, bounded

occurrences MAX-2SAT, and bounded degree Node Cover. We

prove also for the first time inapproximability of the

problem of Sorting by ...
more >>>

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

Piotr Berman, Marek Karpinski

Improved inaproximability results are given, including the

best up to date explicit approximation thresholds for bounded

occurence satisfiability problems, like MAX-2SAT and E2-LIN-2,

and problems in bounded degree graphs, like MIS, Node Cover

and MAX CUT. We prove also for the first time inapproximability

more >>>

Piotr Berman, Marek Karpinski

This paper studies the existence of efficient (small size)

amplifiers for proving explicit inaproximability results for bounded degree

and bounded occurrence combinatorial optimization problems, and gives

an explicit construction for such amplifiers. We use this construction

also later to improve the currently best known approximation lower bounds

more >>>

Irit Dinur, Shmuel Safra

We show Minimum Vertex Cover NP-hard to approximate to within a factor

of 1.3606. This improves on the previously known factor of 7/6.

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.

Janka Chlebíková, Miroslav Chlebik

The paper contributes to the systematic study (started by Berman and

Karpinski) of explicit approximability lower bounds for small occurrence optimization

problems. We present parametrized reductions for some packing and

covering problems, including 3-Dimensional Matching, and prove the best

known inapproximability results even for highly restricted versions of ...
more >>>

Piotr Berman, Marek Karpinski

We improve a number of approximation lower bounds for

bounded occurrence optimization problems like MAX-2SAT,

E2-LIN-2, Maximum Independent Set and Maximum-3D-Matching.

Piotr Berman, Marek Karpinski, Alexander D. Scott

We study approximation hardness and satisfiability of bounded

occurrence uniform instances of SAT. Among other things, we prove

the inapproximability for SAT instances in which every clause has

exactly 3 literals and each variable occurs exactly 4 times,

and display an explicit ...
more >>>

Piotr Berman, Marek Karpinski, Alexander D. Scott

We prove approximation hardness of short symmetric instances

of MAX-3SAT in which each literal occurs exactly twice, and

each clause is exactly of size 3. We display also an explicit

approximation lower bound for that problem. The bound two on

the number ...
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 >>>

Janka Chlebíková, Miroslav Chlebik

Recently Bansal and Sviridenko (Proc. of the 15th SODA'04, 189-196)

proved that for

2-dimensional Orthogonal Rectangle

Bin Packing without rotations allowed there is no asymptotic PTAS, unless P=NP. We show that similar

approximation hardness results hold for several rectangle packing and covering problems even if rotations by ninety

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

Marek Karpinski, Richard Schmied

We study the approximation hardness of the Shortest Superstring, the Maximal Compression and

the Maximum Asymmetric Traveling Salesperson (MAX-ATSP) problem.

We introduce a new reduction method that produces strongly restricted instances of

the Shortest Superstring problem, in which the maximal orbit size is eight

(with no ...
more >>>

Marek Karpinski, Richard Schmied

We develop a new method for proving explicit approximation lower bounds for TSP problems with bounded metrics improving on the best up to now known bounds. They almost match the best known bounds for unbounded metric TSP problems. In particular, we prove the best known lower bound for TSP with ... more >>>

Marek Karpinski, Michael Lampis, Richard Schmied

In this paper, we study the approximability of the metric Traveling Salesman Problem, one of the most widely studied problems in combinatorial optimization. Currently, the best known hardness of approximation bounds are 185/184 for the symmetric case (due to Lampis) and 117/116 for the asymmetric case (due to Papadimitriou and ... more >>>

Marek Karpinski, Richard Schmied

We prove explicit approximation hardness results for the Graphic TSP on cubic and subcubic graphs as well as the new inapproximability bounds for the corresponding instances of the (1,2)-TSP. The proof technique uses new modular constructions of simulating gadgets for the restricted cubic and subcubic instances. The modular constructions used ... more >>>

Peter Floderus, Andrzej Lingas, Mia Persson, Dzmitry Sledneu

We study the complexity of detecting monomials

with special properties in the sum-product

expansion of a polynomial represented by an arithmetic

circuit of size polynomial in the number of input

variables and using only multiplication and addition.

We focus on monomial properties expressed in terms

of the number of distinct ...
more >>>