Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Moses Charikar:

TR07-108 | 27th October 2007
Moses Charikar, Konstantin Makarychev, Yury Makarychev

Local Global Tradeoffs in Metric Embeddings

Suppose that every k points in a n point metric space X are D-distortion embeddable into l_1. We give upper and lower bounds on the distortion required to embed the entire space X into l_1. This is a natural mathematical question and is also motivated by the study of relaxations ... more >>>

TR07-104 | 15th September 2007
Moses Charikar, Konstantin Makarychev, Yury Makarychev

On the Advantage over Random for Maximum Acyclic Subgraph

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

TR06-064 | 1st May 2006
Moses Charikar, Konstantin Makarychev, Yury Makarychev

Note on MAX 2SAT

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

TR06-063 | 1st May 2006
Moses Charikar, Konstantin Makarychev, Yury Makarychev

Approximation Algorithm for the Max k-CSP Problem

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

TR00-001 | 14th January 2000
Piotr Berman, Moses Charikar, Marek Karpinski

On-Line Load Balancing for Related Machines

We consider the problem of scheduling permanent jobs on related machines
in an on-line fashion. We design a new algorithm that achieves the
competitive ratio of $3+\sqrt{8}\approx 5.828$ for the deterministic
version, and $3.31/\ln 2.155 \approx 4.311$ for its randomized variant,
improving the previous competitive ratios ... more >>>

ISSN 1433-8092 | Imprint