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