Abstrakt. Vi visar att alla polygonala indelningar i planet kan omvandlas till en "mgiljotin" indelning vars längd är som mest (1 + c m ) gånger den ursprungliga indelningen, för en liten konstant c. "m-Guillotine" indelningar har en enkel rekursiv struktur som gör att man kan söka efter den kortaste av sådana indelningar i polynom tid, med hjälp av dynamisk programmering. I synnerhet, en konsekvens av vår huvudteoremet är en enkel polynom-tids approximation system för geometriska fall av flera nätverksoptimering problem, inklusive Steiner minsta spännvidd träd, den resande säljare problem (TSP), och k-MST problem. Nyckelord. approximation algoritmer, polynom-tids approximation system, resande säljare problem, k-MST, Steiner minimala träd, giljotin underindelningar, beräkning geometri AMS ämnesklassificeringar. 68Q25, 68R10, 68U05 PII. S0097539796309764 1. Inledning. Vi får en enkel polynom-tids approximation system för geometriska instanser av vissa nätoptimering problem, inklusive Steiner minimum spanning träd, den resande säljare problem (TSP), och k-MST problem. Metoden bygger på begreppet "m-giljotin underindelning", en enkel utvidgning av den senaste approximationsmetoden Mitchell [9], som beaktade fallet m = 1. Grovt sagt är en "m-guillotin-delsektion" en månghörning med egenskapen att det finns en linje ("cut"), vars skärningspunkt med delsektionskanterna består av ett litet antal (O(m) anslutna komponenter, och delområdena på vardera sidan av linjen är också m-guillotin. Den övre gränsen på antalet anslutna komponenter gör det möjligt att tillämpa dynamisk programmering för att optimera över m-giljotin underavdelningar, eftersom det finns en kortfattad specifikation av hur subproblem interagerar över ett snitt. Nyckeln till vår metod är ett teorem som visar att alla polygonala indelningar kan omvandlas till en m-giljotin uppdelning genom att lägga till en uppsättning kanter vars totala längd är liten: som mest
En annan planar indelning, nämligen giljotinen indelning, infördes av Mitchell REF för geometriska optimeringsproblem i planet.
Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
{'venue': 'SIAM J. Comput.', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}