On Guillotine Cutting Sequences

Zitieren

Dateien zu dieser Ressource

Prüfsumme: MD5:6a3c1ae599be17748d99b43463913fc7

ABED, Fidaa, Parinya CHALERMSOOK, José CORREA, Andreas KARRENBAUER, Pablo PÉREZ-LANTERO, José A. SOTO, Andreas WIESE, 2015. On Guillotine Cutting Sequences. 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems. Princeton, USA, 24. Aug 2015 - 26. Aug 2015. In: GARG, Naveen, ed. and others. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems. Princeton, USA, 24. Aug 2015 - 26. Aug 2015. Wadern:Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp. 1-19. eISSN 1868-8969. ISBN 978-3-939897-89-7

@inproceedings{Abed2015Guill-33469, title={On Guillotine Cutting Sequences}, year={2015}, doi={10.4230/LIPIcs.APPROX-RANDOM.2015.1}, number={40}, isbn={978-3-939897-89-7}, address={Wadern}, publisher={Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, series={LIPIcs-Leibniz International Proceedings in Informatics}, booktitle={Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques}, pages={1--19}, editor={Garg, Naveen}, author={Abed, Fidaa and Chalermsook, Parinya and Correa, José and Karrenbauer, Andreas and Pérez-Lantero, Pablo and Soto, José A. and Wiese, Andreas} }

<rdf:RDF xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:dcterms="http://purl.org/dc/terms/" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.uni-konstanz.de/rdf/resource/123456789/33469"> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2016-03-24T12:35:31Z</dcterms:available> <dc:contributor>Pérez-Lantero, Pablo</dc:contributor> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/33469"/> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2016-03-24T12:35:31Z</dc:date> <dc:contributor>Soto, José A.</dc:contributor> <dc:contributor>Karrenbauer, Andreas</dc:contributor> <dcterms:issued>2015</dcterms:issued> <dcterms:rights rdf:resource="http://nbn-resolving.de/urn:nbn:de:bsz:352-20150914100631302-4485392-8"/> <dc:contributor>Chalermsook, Parinya</dc:contributor> <dc:creator>Pérez-Lantero, Pablo</dc:creator> <dcterms:title>On Guillotine Cutting Sequences</dcterms:title> <dc:creator>Wiese, Andreas</dc:creator> <dcterms:abstract xml:lang="eng">Imagine a wooden plate with a set of non-overlapping geometric objects painted on it. How many of them can a carpenter cut out using a panel saw making guillotine cuts, i.e., only moving forward through the material along a straight line until it is split into two pieces? Already fifteen years ago, Pach and Tardos investigated whether one can always cut out a constant fraction if all objects are axis-parallel rectangles. However, even for the case of axis-parallel squares this question is still open. In this paper, we answer the latter affirmatively. Our result is constructive and holds even in a more general setting where the squares have weights and the goal is to save as much weight as possible. We further show that when solving the more general question for rectangles affirmatively with only axis-parallel cuts, this would yield a combinatorial O(1)-approximation algorithm for the Maximum Independent Set of Rectangles problem, and would thus solve a long-standing open problem. In practical applications, like the mentioned carpentry and many other settings, we can usually place the items freely that we want to cut out, which gives rise to the two-dimensional guillotine knapsack problem: Given a collection of axis-parallel rectangles without presumed coordinates, our goal is to place as many of them as possible in a square-shaped knapsack respecting the constraint that the placed objects can be separated by a sequence of guillotine cuts. Our main result for this problem is a quasi-PTAS, assuming the input data to be quasi-polynomially bounded integers. This factor matches the best known (quasi-polynomial time) result for (non-guillotine) two-dimensional knapsack.</dcterms:abstract> <dc:language>eng</dc:language> <dc:creator>Karrenbauer, Andreas</dc:creator> <dc:creator>Chalermsook, Parinya</dc:creator> <dc:contributor>Correa, José</dc:contributor> <dc:creator>Abed, Fidaa</dc:creator> <dc:contributor>Wiese, Andreas</dc:contributor> <dc:creator>Correa, José</dc:creator> <dc:creator>Soto, José A.</dc:creator> <dc:contributor>Abed, Fidaa</dc:contributor> </rdf:Description> </rdf:RDF>

Dateiabrufe seit 24.03.2016 (Informationen über die Zugriffsstatistik)

Abed_0-318529.pdf 57

Das Dokument erscheint in:

KOPS Suche


Stöbern

Mein Benutzerkonto