Report Number: CS-TN-96-39
Institution: Stanford University, Department of Computer Science
Title: Complexity Measures for Assembly Sequences
Author: Goldwasser, Michael
Author: Motwani, Rajeev
Date: December 1996
Abstract: Our work examines various complexity measures for two-handed assembly sequences. Although there has been a great deal of algorithmic success for finding feasible assembly sequences, there has been very little success towards optimizing the costs of sequences. We attempt to explain this lack of progress, by proving the inherent difficulty in finding optimal, or even near-optimal, assembly sequences. We begin by introducing a formal framework for studying the optimization of several complexity measures. We consider a variety of different settings and natural cost measures for assembly sequences. Following which, we define a graph-theoretic problem which is a generalization of assembly sequencing. For our virtual assembly sequencing problem we are able to use techniques common to the theory of approximability to prove the hardness of finding even near-optimal sequences for most cost measures in our generalized framework. Of course, hardness results in our generalized framework do not immediately carry over to the original geometric problems. We continue by realizing several of these hardness results in rather simple geometric settings, proving the difficulty of some of the original problems. These inapproximability results, to the best of our knowledge, are the strongest hardness results known for a purely combinatorial problem in a geometric setting.