The Complexity of Approximation Reoptimization Algorithms for Discrete Optimization

Victor A. Mikhailyuk ()
Additional contact information
Victor A. Mikhailyuk: Lesya Ukrainka Eastern European National University

A chapter in Optimization Methods and Applications, 2017, pp 313-344 from Springer

Abstract: Abstract The objective of postoptimality analysis and reoptimization using approximation methods is applying knowledge of the solution of the initial instance I of the problem (problem with the set values of input parameters) in order to either achieve a better quality of approximation (approximation ratio) of I′ (revised instance) or create a more efficient algorithm for determining an optimal or close to optimal solution of I′. This paper offers theoretical foundations for the acquisition, exploration, and use of bounds in the postoptimality analysis, as well as further development and improvement of approximation algorithms of reoptimization for discrete optimization problems. In particular, the upper and lower bounds on approximation ratio of approximate reoptimization algorithms for the constraint satisfaction problems (CSPs) are obtained using linear and semidefinite relaxations of the initial problem. In addition, sufficient conditions for the existence of polynomial approximation or threshold reoptimization algorithms for CSPs are obtained.

Date: 2017
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-319-68640-0_16

Ordering information: This item can be ordered from
http://www.springer.com/9783319686400

DOI: 10.1007/978-3-319-68640-0_16

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().