Marek Karpinski, Alexander Zelikovsky

The Steiner tree problem requires to find a shortest tree connection

a given set of terminal points in a metric space. We suggest a better

and fast heuristic for the Steiner problem in graphs and in

rectilinear plane. This heuristic finds a Steiner tree at ...
more >>>

Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh Vazirani

We attempt to reconcile the two distinct views of approximation

classes: syntactic and computational.

Syntactic classes such as MAX SNP allow for clean complexity-theoretic

results and natural complete problems, while computational classes such

as APX allow us to work with problems whose approximability is

well-understood. Our results give a computational ...
more >>>

Marek Karpinski, Alexander Zelikovsky

The Steiner tree problem asks for the shortest tree connecting

a given set of terminal points in a metric space. We design

new approximation algorithms for the Steiner tree problems

using a novel technique of choosing Steiner points in dependence

on the possible deviation from ...
more >>>

Petr Slavik

We establish significantly improved bounds on the performance of the greedy

algorithm for approximating MINIMUM SET COVER and MINIMUM PARTIAL COVER. Our

improvements result from a new approach to both problems. In particular,

(a) we improve the known bound on the performance ratio of the greedy ...
more >>>

Oded Goldreich, Dana Ron

In this paper, we consider the question of determining whether

a function $f$ has property $P$ or is $\e$-far from any

function with property $P$.

The property testing algorithm is given a sample of the value

of $f$ on instances drawn according to some distribution.

In some cases,

more >>>

Sanjeev Khanna, Madhu Sudan, David P. Williamson

In this paper we study the approximability of boolean constraint

satisfaction problems. A problem in this class consists of some

collection of ``constraints'' (i.e., functions

$f:\{0,1\}^k \rightarrow \{0,1\}$); an instance of a problem is a set

of constraints applied to specified subsets of $n$ boolean

variables. Schaefer earlier ...
more >>>

Sanjeev Khanna, Madhu Sudan, Luca Trevisan

This paper continues the work initiated by Creignou [Cre95] and

Khanna, Sudan and Williamson [KSW96] who classify maximization

problems derived from boolean constraint satisfaction. Here we

study the approximability of {\em minimization} problems derived

thence. A problem in this framework is characterized by a

collection F ...
more >>>

Marco Cesati, Luca Trevisan

A polynomial time approximation scheme (PTAS) for an optimization

problem $A$ is an algorithm that on input an instance of $A$ and

$\epsilon > 0$ finds a $(1+\epsilon)$-approximate solution in time

that is polynomial for each fixed $\epsilon$. Typical running times

are $n^{O(1/\epsilon)}$ or $2^{1/\epsilon^{O(1)}} ...
more >>>

Marek Karpinski, Alexander Zelikovsky

We study dense instances of several covering problems. An instance of

the set cover problem with $m$ sets is dense if there is $\epsilon>0$

such that any element belongs to at least $\epsilon m$ sets. We show

that the dense set cover problem can be approximated with ...
more >>>

Marek Karpinski, Juergen Wirtgen, Alexander Zelikovsky

The bandwidth problem is the problem of numbering 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

is known to be NP-complete Papadimitriou [Pa76]. Only few special

cases ...
more >>>

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.

Dorit Dor, Shay Halperin, Uri Zwick

Let G=(V,E) be an unweighted undirected graph on n vertices. A simple

argument shows that computing all distances in G with an additive

one-sided error of at most 1 is as hard as Boolean matrix

multiplication. Building on recent work of Aingworth, Chekuri and

Motwani, we describe an \tilde{O}(min{n^{3/2}m^{1/2},n^{7/3}) time

more >>>

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

Oded Goldreich

We consider the question of determining whether

a given object has a predetermined property or is ``far'' from any

object having the property.

Specifically, objects are modeled by functions,

and distance between functions is measured as the fraction

of the domain on which the functions differ.

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

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

Dimitris Fotakis, Paul Spirakis

In this work, we study two special cases of the metric Travelling Salesman

Problem, Graph TSP and TSP(1,2). At first, we show that dense instances of

TSP(1,2) and Graph TSP are essentially as hard to approximate as general

instances of TSP(1,2).

Next, we present an NC algorithm for TSP(1,2) that ... 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 >>>

Ilya Dumer, Daniele Micciancio, Madhu Sudan

We show that the minimum distance of a linear code (or

equivalently, the weight of the lightest codeword) is

not approximable to within any constant factor in random polynomial

time (RP), unless NP equals RP.

Under the stronger assumption that NP is not contained in RQP

(random ...
more >>>

Johan Hastad

We prove that any constraint satisfaction problem

where each variable appears a bounded number of

times admits a nontrivial polynomial time approximation

algorithm.

Pavlos S. Efraimidis, Paul Spirakis

The problem of Scheduling $n$ Independent Jobs

on $m$ Unrelated Parallel Machines, when $m$

is fixed, is considered. The standard problem

of minimizing the makespan of the schedule

(SUM) and the bicriteria problem of scheduling

with bounded makespan and cost (SUMC), are

addressed, and randomized fully linear time

more >>>

Edward Hirsch

During the past three years there was an explosion of algorithms

solving MAX-SAT and MAX-2-SAT in worst-case time of the order

c^K, where c<2 is a constant, and K is the number of clauses

in the input formula. Such bounds w.r.t. the number of variables

instead of the number of ...
more >>>

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

Tobias Polzin, Siavash Vahdati Daneshmand

We study several old and new algorithms for computing lower

and upper bounds for the Steiner problem in networks using dual-ascent

and primal-dual strategies. These strategies have been proven to be

very useful for the algorithmic treatment of the Steiner problem. We

show that none of the known algorithms ...
more >>>

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

Venkatesan Guruswami, Sanjeev Khanna

We give a new proof showing that it is NP-hard to color a 3-colorable

graph using just four colors. This result is already known (Khanna,

Linial, Safra 1992), but our proof is novel as it does not rely on

the PCP theorem, while the earlier one does. This ...
more >>>

Mark Jerrum, Eric Vigoda

We present a fully-polynomial randomized approximation scheme

for computing the permanent of an arbitrary matrix

with non-negative entries.

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.

Piotr Berman, Marek Karpinski

We consider the following optimization problem:

given a system of m linear equations in n variables over a certain field,

a feasible solution is any assignment of values to the variables, and the

minimized objective function is the number of equations that are not

satisfied. For ...
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 >>>

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

Michal Parnas, Dana Ron, Alex Samorodnitsky

We consider the problem of determining whether a given

function f : {0,1}^n -> {0,1} belongs to a certain class

of Boolean functions F or whether it is far from the class.

More precisely, given query access to the function f and given

a distance parameter epsilon, we would ...
more >>>

Piotr Berman, Marek Karpinski

We give improved trade-off results on approximating general

minimum cost scheduling problems.

Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski

We present a new efficient sampling method for approximating

r-dimensional Maximum Constraint Satisfaction Problems, MAX-rCSP, on

n variables up to an additive error \epsilon n^r.We prove a new

general paradigm in that it suffices, for a given set of constraints,

to pick a small uniformly random ...
more >>>

Piotr Berman, Marek Karpinski, Yakov Nekrich

In this paper we present some new results on the approximate parallel

construction of Huffman codes. Our algorithm achieves linear work

and logarithmic time, provided that the initial set of elements

is sorted. This is the first parallel algorithm for that problem

with the optimal time and ...
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.

Wenceslas Fernandez de la Vega, Marek Karpinski

We prove that MAX-3SAT can be approximated in polynomial time

within a factor 9/8 on random instances.

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.

Birgit Schelm

Both average-case complexity and the study of the approximability properties of NP-optimization problems are well established and active fields of research. By applying the notion of average-case complexity to approximation problems we provide a formal framework that allows the classification of NP-optimization problems according to their average-case approximability. Thus, known ... more >>>

Andreas Björklund, Thore Husfeldt, Sanjeev Khanna

We investigate the hardness of approximating the longest path and

the longest cycle in directed graphs on $n$ vertices. We show that

neither of these two problems can be polynomial time approximated

within $n^{1-\epsilon}$ for any $\epsilon>0$ unless

$\text{P}=\text{NP}$. In particular, the result holds for

more >>>

Eran Halperin, Guy Kortsarz, Robert Krauthgamer

In the {\sc $k$-center} problem, the input is a bound $k$

and $n$ points with the distance between every two of them,

such that the distances obey the triangle inequality.

The goal is to choose a set of $k$ points to serve as centers,

so that the maximum distance ...
more >>>

Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Seffi Naor

We show that the asymmetric $k$-center problem is

$\Omega(\log^* n)$-hard to approximate unless

${\rm NP} \subseteq {\rm DTIME}(n^{poly(\log \log n)})$.

Since an $O(\log^* n)$-approximation algorithm is known

for this problem, this essentially resolves the approximability

of this problem. This is the first natural problem

whose approximability threshold does not polynomially ...
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 >>>

Michal Parnas, Dana Ron, Ronitt Rubinfeld

A standard property testing algorithm is required to determine

with high probability whether a given object has property

P or whether it is \epsilon-far from having P, for any given

distance parameter \epsilon. An object is said to be \epsilon-far

from having ...
more >>>

Zdenek Dvorák, Daniel Král, Ondrej Pangrác

An instance of a constraint satisfaction problem is $l$-consistent

if any $l$ constraints of it can be simultaneously satisfied.

For a set $\Pi$ of constraint types, $\rho_l(\Pi)$ denotes the largest ratio of constraints which can be satisfied in any $l$-consistent instance composed by constraints from the set $\Pi$. In the ...
more >>>

Uriel Feige, Daniel Reichman

Max-Satisfy is the problem of finding an assignment that satisfies

the maximum number of equations in a system of linear equations

over $\mathbb{Q}$. We prove that unless NP$\subseteq $BPP there is no

polynomial time algorithm for the problem achieving an

approximation ratio of $1/n^{1-\epsilon}$, where $n$ is the number

of ...
more >>>

Frank Neumann, Marco Laumanns

We give faster approximation algorithms for the

generalization of two NP-hard spanning tree problems. First,

we investigate the problem of minimizing the degree of

minimum spanning forests. The task is to compute for each

number of connected components a minimum spanning forest

whose degree is as small as possible. Fischer

more >>>

Piotr Berman, Marek Karpinski

We design a polynomial time 8/7-approximation algorithm for the Traveling Salesman Problem in which all distances are either one or two. This improves over the best known approximation factor of 7/6 for that problem. As a direct application we get a 7/6-approximation algorithm for the Maximum Path Cover Problem, similarily ... more >>>

Michal Parnas, Dana Ron

We consider the problem of estimating the size, $VC(G)$, of a

minimum vertex cover of a graph $G$, in sublinear time,

by querying the incidence relation of the graph. We say that

an algorithm is an $(\alpha,\eps)$-approximation algorithm

if it outputs with high probability an estimate $\widehat{VC}$

such that ...
more >>>

Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Amir Shpilka, Adam Smith

We raise the question of approximating compressibility of a string with respect to a fixed compression scheme, in sublinear time. We study this question in detail for two popular lossless compression schemes: run-length encoding (RLE) and Lempel-Ziv (LZ), and present algorithms and lower bounds for approximating compressibility with respect to ... more >>>

Don Coppersmith, Lisa Fleischer, Atri Rudra

We consider the following simple algorithm for feedback arc set problem in weighted tournaments --- order the vertices by their weighted indegrees. We show that this algorithm has an approximation guarantee of $5$ if the weights satisfy \textit{probability constraints}

(for any pair of vertices $u$ and $v$, $w_{uv}+w_{vu}=1$). Special cases ...
more >>>

Jan Arpe, Bodo Manthey

Given a set of monomials, the Minimum AND-Circuit problem asks for a

circuit that computes these monomials using AND-gates of fan-in two and

being of minimum size. We prove that the problem is not polynomial time

approximable within a factor of less than 1.0051 unless P = NP, even if

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

Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski

We study the problem of absolute approximability of MAX-CSP problems with the global constraints. We prove existence of an efficient sampling method for the MAX-CSP class of problems with linear global constraints and bounded feasibility gap. It gives for the first time a polynomial in epsilon^-1 sample complexity bound for ... more >>>

Konstantinos Georgiou, Avner Magen, Iannis Tourlakis

We prove that the integrality gap after tightening the standard LP relaxation for Vertex Cover with Omega(sqrt(log n/log log n)) rounds of the SDP LS+ system is 2-o(1).

more >>>Bodo Manthey

A cycle cover of a graph is a set of cycles such that every vertex is

part of exactly one cycle. An L-cycle cover is a cycle cover in which

the length of every cycle is in the set L. The weight of a cycle cover

of an edge-weighted graph ...
more >>>

Patrick Briest, Martin Hoefer, Piotr Krysta

We study a multi-player one-round game termed Stackelberg Network Pricing Game, in which a leader can set prices for a subset of m pricable edges in a graph. The other edges have a fixed cost. Based on the leader's decision one or more followers optimize a polynomial-time solvable combinatorial minimization ... more >>>

Yijia Chen, Martin Grohe, Magdalena Grüber

Combining classical approximability questions with parameterized complexity, we introduce a theory of parameterized approximability.

The main intention of this theory is to deal with the efficient approximation of small cost solutions for optimisation problems.

Piotr Berman, Bhaskar DasGupta, Marek Karpinski

We consider <i>minimum equivalent digraph</i> (<i>directed network</i>) problem (also known as the <i>strong transitive reduction</i>), its maximum optimization variant, and some extensions of those two types of problems. We prove the existence of polynomial time approximation algorithms with ratios 1.5 for all the minimization problems and 2 for all the ... more >>>

Piotr Berman, Marek Karpinski, Alexander Zelikovsky

We give a 1.25 approximation algorithm for the Steiner Tree Problem with distances one and two, improving on the best known bound for that problem.

more >>>Marek Karpinski, Warren Schudy

We design a linear time approximation scheme for the Gale-Berlekamp Switching Game and generalize it to a wider class of dense fragile minimization problems including the Nearest Codeword Problem (NCP) and Unique Games Problem. Further applications include, among other things, finding a constrained form of matrix rigidity and maximum likelihood ... more >>>

Christian Glaßer, Christian Reitwießner, Maximilian Witek

We improve and derandomize the best known approximation algorithm for the two-criteria metric traveling salesman problem (2-TSP). More precisely, we construct a deterministic 2-approximation which answers an open question by Manthey.

Moreover, we show that 2-TSP is randomized $(3/2+\epsilon ,2)$-approximable, and we give the first randomized approximations for the two-criteria ... more >>>

Sanjeev Arora, Russell Impagliazzo, William Matthews, David Steurer

We present two new approximation algorithms for Unique Games. The first generalizes the results of Arora, Khot, Kolla, Steurer, Tulsiani, and Vishnoi who give polynomial time approximation algorithms for graphs with high conductance. We give a polynomial time algorithm assuming only good local conductance, i.e. high conductance for small subgraphs. ... more >>>

Mahdi Cheraghchi, Johan Hastad, Marcus Isaksson, Ola Svensson

We study constraint satisfaction problems on the domain $\{-1,1\}$, where the given constraints are homogeneous linear threshold predicates. That is, predicates of the form $\mathrm{sgn}(w_1 x_1 + \cdots + w_n x_n)$ for some positive integer weights $w_1, \dots, w_n$. Despite their simplicity, current techniques fall short of providing a classification ... 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 >>>

Scott Aaronson, Travis Hance

Around 2002, Leonid Gurvits gave a striking randomized algorithm to approximate the permanent of an n×n matrix A. The algorithm runs in O(n^2/?^2) time, and approximates Per(A) to within ±?||A||^n additive error. A major advantage of Gurvits's algorithm is that it works for arbitrary matrices, not just for nonnegative matrices. ... 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 >>>

Uriel Feige, Rani Izsak

Given a set of items and a collection of players, each with a nonnegative monotone valuation set function over the items,

the welfare maximization problem requires that every item be allocated to exactly one player,

and one wishes to maximize the sum of values obtained by the players,

as computed ...
more >>>

Marek Karpinski

We present in this paper some of the recent techniques and methods for proving best up to now explicit approximation hardness bounds for metric symmetric and asymmetric Traveling Salesman Problem (TSP) as well as related problems of Shortest Superstring and Maximum Compression. We attempt to shed some light on the ... more >>>