JavaScript is disabled for your browser. Some features of this site may not work without it.
An Incremental Model for Combinatorial Minimization

Author
Hartline, Jeff; Sharp, Alexa
Abstract
Traditional optimization algorithms are concerned with static input,
static constraints, and attempt to produce static output of optimal value. Recent literature has strayed from this conventional approach to deal with more realistic situations in which the input changes over time. Incremental optimization is a new framework for handling this type of dynamic behavior. We consider a general model for producing incremental versions of traditional covering problems along with several natural incremental metrics. Using this model, we demonstrate how to convert conventional algorithms into incremental algorithms with only a constant factor loss in approximation power. We introduce incremental versions of min cut, edge cover, and (k, r)-center and present some hardness results. Lastly, we discuss how the incremental model can help us more fully understand online problems and their corresponding algorithms.
Date Issued
2006-07-05Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cis/TR2006-2034
Type
technical report