Rohit Khandekar and Subhash A. Khot and Lorenzo Orecchia and Nisheeth K. Vishnoi

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2007-177

December 22, 2007

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-177.pdf

We study the following game between a ``cut'' player C and a ``matching'' player M. The game starts with an empty graph G on a set V of n vertices. In each round, the cut player chooses a bisection (S,V\S) of vertices and the matching player then adds a perfect matching M (not necessarily belonging to G) between S and V\S to the (multi-)graph G. The choices of the players in each round may depend on those in the previous rounds. The game ends when G becomes an edge-expander. The value of this game, denoted by Val(n,C,M), is the total number of rounds in the game before it ends. We study this game for its connection with the Sparsest Cut problem in undirected graphs: if there is a polynomial-time cut player C such that Val(n,C,M) < f(n) for all M, then there is a polynomial-time O(f(n))-approximation algorithm for the Sparsest Cut problem.

We show that there is no cut player C, even unbounded-time, that can ensure Val(n,C,M) = o(GAP(n)<SUP>1/2</SUP>) for all matching players M, where GAP(n) is the integrality gap of the well-studied SDP with triangle inequality constraints for the Sparsest Cut problem. Recall that GAP(n) = Omega(log log n). Thus, we prove that this approach cannot yield a o(GAP(n)<SUP>1/2</SUP>)-approximation (and in particular, o((log log n)<SUP>1/2</SUP>)-approximation) algorithm for this problem. Furthermore, we show that there is a (super-polynomial time) cut player C* such that, for all M, we have Val(n,C*,M) = O(log n).

---

BibTeX citation:

@techreport{Khandekar:EECS-2007-177,
    Author= {Khandekar, Rohit and Khot, Subhash A. and Orecchia, Lorenzo and Vishnoi, Nisheeth K.},
    Title= {On a Cut-Matching Game for the Sparsest Cut Problem},
    Year= {2007},
    Month= {Dec},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-177.html},
    Number= {UCB/EECS-2007-177},
    Abstract= {We study the following game between a ``cut'' player C and a
``matching'' player M. The game starts with an empty graph G on a set V of
n vertices. In each round, the cut player chooses a bisection
(S,V\S) of vertices and the matching player then adds a perfect
matching M (not necessarily belonging to G) between S and V\S
to the (multi-)graph G. The choices of the players in each round may
depend on those in the previous rounds. The game ends when G becomes
an edge-expander. The value of this game, denoted by Val(n,C,M),
is the total number of rounds in the game before it ends. We study
this game for its connection with the Sparsest Cut problem in undirected
graphs: if there is a polynomial-time cut player C such that
Val(n,C,M) < f(n) for all M, then there is a
polynomial-time O(f(n))-approximation algorithm for the Sparsest Cut
problem.

We show that there is no cut player C, even unbounded-time, that
can ensure Val(n,C,M) = o(GAP(n)<SUP>1/2</SUP>) for all matching
players M, where GAP(n) is the integrality gap of the
well-studied SDP with triangle inequality constraints for the
Sparsest Cut problem. Recall that GAP(n) = Omega(log log
n). Thus, we prove that this approach cannot yield a
o(GAP(n)<SUP>1/2</SUP>)-approximation (and in particular, o((log
log n)<SUP>1/2</SUP>)-approximation) algorithm for this problem. Furthermore, we
show that there is a (super-polynomial time) cut player C* such
that, for all M, we have Val(n,C*,M) = O(log n).},
}

EndNote citation:

%0 Report
%A Khandekar, Rohit 
%A Khot, Subhash A. 
%A Orecchia, Lorenzo 
%A Vishnoi, Nisheeth K. 
%T On a Cut-Matching Game for the Sparsest Cut Problem
%I EECS Department, University of California, Berkeley
%D 2007
%8 December 22
%@ UCB/EECS-2007-177
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-177.html
%F Khandekar:EECS-2007-177