Framework for er-completeness of two-dimensional packing problems

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

We show that many natural two-dimensional packing problems are algorithmically equivalent to finding real roots of multivariate polynomials. A two-dimensional packing problem is defined by the type of pieces, containers, and motions that are allowed. The aim is to decide if a given set of pieces can be placed inside a given container. The pieces must be placed so that in the resulting placement, they are pairwise interior-disjoint, and only motions of the allowed type can be used to move them there. We establish a framework which enables us to show that for many combinations of allowed pieces, containers, and motions, the resulting problem is ER-complete. This means that the problem is equivalent (under polynomial time reductions) to deciding whether a given system of polynomial equations and inequalities with integer coefficients has a real solution. A full version of this extended abstract is available on https://arxiv.org/abs/1704.06969.

OriginalsprogEngelsk
TitelProceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020
ForlagIEEE Computer Society Press
Publikationsdato2020
Sider1014-1021
Artikelnummer9317895
ISBN (Elektronisk)9781728196213
DOI
StatusUdgivet - 2020
Begivenhed61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020 - Virtual, Durham, USA
Varighed: 16 nov. 202019 nov. 2020

Konference

Konference61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020
LandUSA
ByVirtual, Durham
Periode16/11/202019/11/2020
SponsorIEEE Computer Society Technical Committee on Mathematical Foundations of Computing

ID: 258402025