Gerhard J. Woeginger

We derive results of the following flavor:

If a combinatorial optimization problem can be formulated via a dynamic

program of a certain structure and if the involved cost and transition

functions satisfy certain arithmetical and structural conditions, then

the optimization problem automatically possesses a fully polynomial time

approximation scheme (FPTAS).

Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani

We give polynomial time approximation schemes for the problem

of partitioning an input set of n points into a fixed number

k of clusters so as to minimize the sum over all clusters of

the total pairwise distances in a cluster. Our algorithms work

for arbitrary metric spaces as well ...
more >>>

Detlef Sieling

Decision trees are representations of discrete functions with widespread applications in, e.g., complexity theory and data mining and exploration. In these areas it is important to obtain decision trees of small size. The minimization problem for decision trees is known to be NP-hard. In this paper the problem is shown ... more >>>

Michelle Effros, Leonard Schulman

We consider the $K$-clustering problem with the $\ell_2^2$

distortion measure, also known as the problem of optimal

fixed-rate vector quantizer design. We provide a deterministic

approximation algorithm which works for all dimensions $d$ and

which, given a data set of size $n$, computes in time

more >>>

George Karakostas

We reduce the approximation factor for Vertex Cover to $2-\Theta(1/\sqrt{logn})$

(instead of the previous $2-\Theta(loglogn/logn})$, obtained by Bar-Yehuda and Even,

and by Monien and Speckenmeyer in 1985. The improvement of the vanishing

factor comes as an application of the recent results of Arora, Rao, and Vazirani

that improved ...
more >>>

MohammadTaghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour

In the buy-at-bulk $k$-Steiner tree (or rent-or-buy

$k$-Steiner tree) problem we are given a graph $G(V,E)$ with a set

of terminals $T\subseteq V$ including a particular vertex $s$ called

the root, and an integer $k\leq |T|$. There are two cost functions

on the edges of $G$, a buy cost $b:E\longrightarrow ...
more >>>

Moses Charikar, Konstantin Makarychev, Yury Makarychev

We present a c.k/2^k approximation algorithm for the Max k-CSP problem (where c > 0.44 is an absolute constant). This result improves the previously best known algorithm by Hast, which has an approximation guarantee of Omega(k/(2^k log k)). Our approximation guarantee matches the upper bound of Samorodnitsky and Trevisan up ... more >>>

Moses Charikar, Konstantin Makarychev, Yury Makarychev

In this note we present an approximation algorithm for MAX 2SAT that given a (1 - epsilon) satisfiable instance finds an assignment of variables satisfying a 1 - O(sqrt{epsilon}) fraction of all constraints. This result is optimal assuming the Unique Games Conjecture.

The best previously known result, due ... more >>>

Xin Han, Kazuo Iwama, Deshi Ye, Guochuan Zhang

In this paper

we establish a general algorithmic framework between bin packing

and strip packing, with which we achieve the same asymptotic

bounds by applying bin packing algorithms to strip packing. More

precisely we obtain the following results: (1) Any offline bin

packing algorithm can be applied to strip packing ...
more >>>

Moses Charikar, Konstantin Makarychev, Yury Makarychev

In this paper we present a new approximation algorithm for the MAX ACYCLIC SUBGRAPH problem. Given an instance where the maximum acyclic subgraph contains (1/2 + delta) fraction of all edges, our algorithm finds an acyclic subgraph with (1/2 + Omega(delta/ log n)) fraction of all edges.

more >>>Konstantin Makarychev, Yury Makarychev

In this note we improve a recent result by Arora, Khot, Kolla, Steurer, Tulsiani, and Vishnoi on solving the Unique Games problem on expanders.

Given a (1 - epsilon)-satisfiable instance of Unique Games with the constraint graph G, our algorithm finds an assignments satisfying at least a (1 - C ... more >>>

Valentin Brimkov, Andrew Leach, Jimmy Wu, Michael Mastroianni

Given a finite set of straight line segments $S$ in $R^{2}$ and some $k\in N$, is there a subset $V$ of points on segments in $S$ with $\vert V \vert \leq k$ such that each segment of $S$ contains at least one point in $V$? This is a special case ... more >>>

Suguru Tamaki, Yuichi Yoshida

A temporal constraint language $\Gamma$ is a set of relations with first-order definitions in $({\mathbb{Q}}; <)$. Let CSP($\Gamma$) denote the set of constraint satisfaction problem instances with relations from $\Gamma$. CSP($\Gamma$) admits robust approximation if, for any $\varepsilon \geq 0$, given a $(1-\varepsilon)$-satisfiable instance of CSP($\Gamma$), we can compute an ... more >>>