All reports by Author Konstantin Makarychev:

__
TR09-021
| 2nd March 2009
__

Konstantin Makarychev, Yury Makarychev#### How to Play Unique Games on Expanders

__
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

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

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