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

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

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

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

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

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

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

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.

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.

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

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.

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

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

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

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

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

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

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

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

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