All reports by Author Moses Charikar:

__
TR07-108
| 27th October 2007
__

Moses Charikar, Konstantin Makarychev, Yury Makarychev#### Local Global Tradeoffs in Metric Embeddings

__
TR07-104
| 15th September 2007
__

Moses Charikar, Konstantin Makarychev, Yury Makarychev#### On the Advantage over Random for Maximum Acyclic Subgraph

__
TR06-064
| 1st May 2006
__

Moses Charikar, Konstantin Makarychev, Yury Makarychev#### Note on MAX 2SAT

__
TR06-063
| 1st May 2006
__

Moses Charikar, Konstantin Makarychev, Yury Makarychev#### Approximation Algorithm for the Max k-CSP Problem

__
TR00-001
| 14th January 2000
__

Piotr Berman, Moses Charikar, Marek Karpinski#### On-Line Load Balancing for Related Machines

Moses Charikar, Konstantin Makarychev, Yury Makarychev

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

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

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

Piotr Berman, Moses Charikar, Marek Karpinski

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