Michael Goldwasser, Princeton University
Intractability of Assembly Sequencing:Unit Disks in the Plane
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. This Disks problem is a
version of a common task in assembly sequencing, namely removing a
given part from a fully assembled product. 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. Namely, we show that approximating the number of
steps required lies in Class III of the Arora/Lund approximation
hierarchy. This provides the first inapproximability results for
assembly sequencing, realized in a geometric setting.