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.