Neighborhood Structures with Approximation Guarantees

We present a set of necessary and sufficient conditions under
which all the locally optimal solutions corresponding to a
neighborhood structure provide an e-approximation for a linear
combinatorial optimization problem. The conditions provide a
common technique of proving the approximation guarantee of a
neighborhood structure. We show the applicability of the technique
by proving some known approximation results that have been proved
using different techniques earlier and also deriving some new
approximation results. We also show that in general, identifying
whether a neighborhood structure does not provide e-approximation
for a linear combinatorial optimization problem can be NP-complete.

Dushyant Sharma is an assistant professor at the department of
industrial and operations engineering at University of Michigan.
He received his bachelor degree in Computer Science from Indian
Institute of Technology in 1996 and Ph.D. in Operations Research
from MIT in 2002. He has research interests in theory and
application of network and discrete optimization, and development
of decision support systems. His past work involves applications
of optimization techniques to scheduling problems in airline,
railroad, and printed circuit board manufacturing, and network
design for telecommunications.