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

3 comments:

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

    ReplyDelete
  2. Good point. let me update the post.

    ReplyDelete
  3. 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

Disqus for The Geomblog