Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, $k$-MST, and Related Problems TeX Export

@article{citeulike:1185603, abstract = {We show that any polygonal subdivision in the plane can be converted into an \"mguillotine \" subdivision whose length is at most (1 + ) times that of the original subdivision, for a small constant c. \"m-Guillotine\" subdivisions have a simple recursive structure that allows one to search for shortest such subdivisions in polynomial time, using dynamic programming. In particular, a consequence of our main theorem is a simple polynomial-time approximation scheme for geometric instances of...}, author = {Mitchell, Joseph S. B.}, citeulike-article-id = {1185603}, citeulike-linkout-0 = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.6348}, journal = {SIAM Journal on Computing}, keywords = {buillotine, geometric, subdivisions, tsp}, number = {4}, pages = {1298--1309}, posted-at = {2007-03-24 22:45:39}, priority = {2}, title = {Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric {TSP}, \$k\$-{MST}, and Related Problems}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.6348}, volume = {28}, year = {1999} }

TY - JOUR ID - citeulike:1185603 L3 - citeulike-article-id:1185603 N2 - We show that any polygonal subdivision in the plane can be converted into an "mguillotine " subdivision whose length is at most (1 + ) times that of the original subdivision, for a small constant c. "m-Guillotine" subdivisions have a simple recursive structure that allows one to search for shortest such subdivisions in polynomial time, using dynamic programming. In particular, a consequence of our main theorem is a simple polynomial-time approximation scheme for geometric instances of... IS - 4 JF - SIAM Journal on Computing EP - 1309 TI - Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric {TSP}, $k$-{MST}, and Related Problems VL - 28 SP - 1298 KW - buillotine KW - geometric KW - subdivisions KW - tsp AU - Mitchell, Joseph PY - 1999/// UR - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.6348 ER -