Many geometric problems (especially those involving rectangles in the plane) are MAX SNP-hard; some are even log n hard via set cover reductions, and there is at least one problem (matching of point sets) that is polynomially hard.
However, as far as I am aware of, most of the reductions are via L-reductions from other hard-to-approximate problems. In fact the only "from first-principles" hardness results for geometric problems (i.e directly from a PCP) that I am aware of are
1. The result by Brieden showing that width is hard to approximate to any constant
2. The extension by Varadarajan, Venkatesh and Zhang that shows it is hard to approximate to within logd n, for some d > 0.
In both cases, the "source" problem is Quadratic Programming. One might quibble that even in this case, the reduction is really an L-reduction from QP, but in both results some tinkering with the PCP is necessary to get the desired bound.
Are there other problems that have "from first principles" hardness results ?
No comments:
Post a Comment