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.
http://i.stanford.edu/pub/cstr/reports/cs/tn/96/39/CS-TN-96-39.pdf