Report Number: CS-TN-96-38
Institution: Stanford University, Department of Computer Science
Title: Intractability of Assembly Sequencing: Unit Disks in the Plane
Author: Goldwasser, Michael
Author: Motwani, Rajeev
Date: December 1996
Abstract: We consider the problem of removing a given disk from a collection of unit disks in the plane. At each step, we allow a disk to be removed by a collision-free translation to infinity, and the goal is to access a given disk using as few steps as possible. Recently there has been a focus on optimizing assembly sequences over various cost measures, however with very limited algorithmic success. We explain this lack of success, proving strong inapproximability results in this simple geometric setting. These inapproximability results, to the best of our knowledge, are the strongest hardness results known for any purely combinatorial problem in a geometric setting. As a stepping stone, we study the approximability of scheduling with AND/OR precedence constraints. The Disks problem can be formulated as a scheduling problem where the order of removals is to be scheduled. Before scheduling a disk to be removed, a path must be cleared, and so we get precedence constraints on the tasks; however, the form of such constraints differs from traditional scheduling in that there is a choice of which path to clear.
http://i.stanford.edu/pub/cstr/reports/cs/tn/96/38/CS-TN-96-38.pdf