Konstantin Makarychev

I graduated from Princeton University in 2007. My advisor was Moses Charikar. Before attending Princeton I was an undergraduate student at the Mathematics Department of Moscow State University. I finished Moscow 57 Math High School.

Publications

On the Integrality Gap for Pricing Items for Single-Minded Bidders,

Rohit Khandekar Tracy Kimbrel, Konstantin Makarychev, Maxim Sviridenko,

manuscript

 

Integrality Gaps for Sherali-Adams Relaxations,

Moses Charikar, Konstantin Makarychev, Yury Makarychev,

manuscript

 

Online Make-to-Order Joint Replenishment Model: Primal Dual Competitive Algorithms,

Niv Buchbinder, Tracy Kimbrel, Retsef Levi, Konstantin Makarychev, Maxim Sviridenko,

SODA 2008, pp. 952 - 961

 

Local Global Tradeoffs in Metric Embeddings,

Moses Charikar, Konstantin Makarychev, Yury Makarychev,

FOCS 2007, pp. 713-723

 

On the Advantage over Random for Maximum Acyclic Subgraph,

Moses Charikar, Konstantin Makarychev, Yury Makarychev,

FOCS 2007, pp. 625-633

 

Near-Optimal Algorithms for Maximum Constraint Satisfaction Problems,

In this paper we study two Maximum Constraint Satisfaction Problems: MAX 2SAT and MAX k-CSP.

For MAX 2SAT, we present an approximation algorithm that given a (1-ε) satisfiable instance finds an assignment of variables satisfying a 1-O(√ε) fraction of all constraints. This result is optimal assuming the Unique Games Conjecture. The best previously known result, due to Zwick, was 1-O(ε^1/3)

For MAX k-CSP, we present a ck/2^k approximation algorithm (where c > 0.44 is an absolute constant). This result improves the previously best known algorithm by Hast, which has an approximation guarantee of   Ω(k/(2^k log k)). Our approximation guarantee matches the upper bound of Samorodnitsky and Trevisan up to a constant factor (their result assumes the Unique Games Conjecture).

Moses Charikar, Konstantin Makarychev, Yury Makarychev,

SODA 2007, pp. 205-214

 

A Divide and Conquer Algorithm for d-Dimensional Linear Arrangement,

Moses Charikar, Konstantin Makarychev, Yury Makarychev,

SODA 2007

 

How to Play Unique Games Using Embeddings,

In this paper we present a new approximation algorithm for Unique Games. For a Unique Game with n vertices and k states, if a (1-ε) fraction of all constraints is satisfiable, the algorithm finds an assignment satisfying a

1-O(ε √ (log n log k))

fraction of all constraints. To this end, we introduce new embedding techniques for rounding semidefinite relaxations of problems with large domain size.

Eden Chlamtac, Konstantin Makarychev, Yury Makarychev,

FOCS 2006, pp. 687-696

 

Near-Optimal Algorithms for Unique Games,

We present approximation algorithms for the Unique Game Problem. For instances with domain size k where the optimal solution satisfies (1 - ε) fraction of all constraints, our algorithms satisfy roughly k^{-½ ε} and 1 - O((ε log k)^½) fraction of all constraints. Our results are near optimal if the Unique Games Conjecture is true.

Moses Charikar, Konstantin Makarychev, Yury Makarychev,

STOC 2006, pp. 205-214

 

Directed Metrics and Directed Graph Partitioning Problems,

In this paper we initiate a study of metric embeddings for directed metrics and their applications to directed partitioning problems. We prove low and upper bounds for the distortion of such embeddings.

Moses Charikar, Konstantin Makarychev, Yury Makarychev,

SODA 2006, pp. 51-60

 

O(sqrt{log n}) approximation algorithms for Min UnCut, Min 2CNF Deletion, and directed cut problems,

We give O(√log n)-approximation algorithms for the Min UnCut, Min 2CNF Deletion, Directed Balanced Separator, and Directed Sparsest Cut problems. The previously best known algorithms give an O(log n)-approximation for Min UnCut, Directed Balanced Separator, Directed Sparsest Cut, and an O(log n log log n)-approximation for Min 2CNF Deletion. We also show that the integrality gap of an SDP relaxation of the Minimum Multicut problem is Ω(log n).

Amit Agarwal, Moses Charikar, Konstantin Makarychev, Yury Makarychev,

STOC 2005, pp. 573-581

 

Quadratic Forms on Graphs,

We introduce a new graph parameter, called the Grothendieck constant of a graph. This parameter is a generalization of the classical Grothendieck constant; and it is equal to an integrality gap of a certain SDP problem, which has various algorithmic applications. Our results improve a recent result of Kashin and Szarek on Gram matrices of uniformly bounded functions, and settle a problem of Megretski and of Charikar and Wirth.

Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor

STOC 2005, pp. 486-493;

Inventiones Mathematicae, vol. 163, no. 3, pp. 499-522, March 2006

 

Conditionally Independent Random Variables,

In this paper we investigate the notion of conditional independence and prove several information inequalities for conditionally independent random variables.

Konstantin Makarychev, Yury Makarychev

Technical Report arXiv:cs.IT/0510029

 

A new class of non Shannon type inequalities for entropies,

In this paper we prove a countable set of non-Shannon-type linear information inequalities for entropies of discrete random variables, i.e., information inequalities which cannot be reduced to the "basic" inequality I(X : Y | Z) > 0. Our results generalize the inequalities of Zhang and Yeung who found the first examples of non-Shannon-type information inequalities.

Konstantin Makarychev, Yury Makarychev, Andrei Romashchenko, Nikolai Vereshchagin

Communications in Information and Systems, vol. 2, no. 2, pp. 147-166, December 2002

 

The Importance of Being Formal,

Konstantin Makarychev, Yury Makarychev

The Mathematical Intelligencer, vol. 23 no. 1, 2001

 

Proof of Pak's conjecture on tilings by T-tetrominoes (in Russian),

Konstantin Makarychev, Yury Makarychev

manuscript