tag:blogger.com,1999:blog-6555947.post4121470039273588874..comments2024-03-14T01:32:43.610-06:00Comments on The Geomblog: Is HAM SANDWICH PPAD-Complete ?Suresh Venkatasubramanianhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-6555947.post-85743618255472950922009-04-10T17:22:00.000-06:002009-04-10T17:22:00.000-06:00AFAIK, both HAM-SANDWICH and NECKLACE-SPLITTING ar...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.Shiva Kintalihttps://www.blogger.com/profile/07853545928906483737noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-16815085039650302652009-04-10T17:09:00.000-06:002009-04-10T17:09:00.000-06:00Good point. let me update the post.Good point. let me update the post.Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-11917189676696853342009-04-10T16:26:00.000-06:002009-04-10T16:26:00.000-06:00What's the exact problem statement you're consider...What's the exact problem statement you're considering? In the plane, Megiddo did it in linear time (JALG '85).Anonymousnoreply@blogger.com