Friday, April 10, 2009

Is HAM SANDWICH PPAD-Complete ?

Reading the algorithmic game theory book, I discover that HAM SANDWICH is in PPAD (not surprising in retrospect when you think of Brouwer's fixed point theorem as the canonical PPAD problem). Is HAM SANDWICH PPAD-Complete ?

Update: I should clarify - this is the problem I'm referring to:
Given n sets of 2n points (each) in n dimensions, is there a single hyperplane that bisects each set (i.e divides it into two sets of size n).

In 2D, the problem is to bisect two sets (the ham and the bread).
Posted by Suresh Venkatasubramanian at 4/10/2009 02:54:00 PM
Labels: , ,

3 comments:

  1. Anonymous4/10/2009 04:26:00 PM

    What's the exact problem statement you're considering? In the plane, Megiddo did it in linear time (JALG '85).

    ReplyDelete
  2. Suresh Venkatasubramanian4/10/2009 05:09:00 PM

    Good point. let me update the post.

    ReplyDelete
  3. Shiva Kintali4/10/2009 05:22:00 PM

    AFAIK, both HAM-SANDWICH and NECKLACE-SPLITTING are in PPAD but not known to be PPAD-complete. Both these problems are mentioned in Papadimitriou's 1994 paper.

    ReplyDelete

Subscribe to: Post Comments (Atom)

Disqus for The Geomblog