Framework for er-completeness of two-dimensional packing problems
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfæ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.
Originalsprog | Engelsk |
---|---|
Titel | Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020 |
Forlag | IEEE Computer Society Press |
Publikationsdato | 2020 |
Sider | 1014-1021 |
Artikelnummer | 9317895 |
ISBN (Elektronisk) | 9781728196213 |
DOI | |
Status | Udgivet - 2020 |
Begivenhed | 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020 - Virtual, Durham, USA Varighed: 16 nov. 2020 → 19 nov. 2020 |
Konference
Konference | 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020 |
---|---|
Land | USA |
By | Virtual, Durham |
Periode | 16/11/2020 → 19/11/2020 |
Sponsor | IEEE Computer Society Technical Committee on Mathematical Foundations of Computing |
ID: 258402025