Luca Trevisan

We consider the Traveling Salesperson Problem (TSP) restricted

to Euclidean spaces of dimension at most k(n), where n is the number of

cities. We are interested in the relation between the asymptotic growth of

k(n) and the approximability of the problem. We show that the problem is ...
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 >>>

Hans-Joachim BĂ¶ckenhauer, Juraj Hromkovic, Ralf Klasing, Sebastian Seibert, Walter Unger

The investigation of the possibility to efficiently compute

approximations of hard optimization problems is one of the central

and most fruitful areas of current algorithm and complexity theory.

The aim of this paper is twofold. First, we introduce the notion of

stability of approximation algorithms. This notion is shown to ...
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 >>>

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

Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz

We study a natural and quite general model of branch-and-bound algorithms. In this model, an algorithm attempts to minimize (or maximize) a function $f : D \to \mathbb{R}_{\geq 0}$ by making oracle queries to a heuristic $h_f$ satisfying

\[

\min_{x \in S} f(x) \leq h_f(S) \leq \gamma \cdot ...
more >>>