Abstract
If an element is inserted into or removed from a set, then the set covering problem can be reoptimized with some ratio \( \left( {2 - \frac{1}{{\ln m + 1}}} \right) \), where m is the number of elements of the set. A similar result holds if an arbitrary number 1 < p < m of elements of the set is inserted or removed.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
G. Ausiello, B. Escoffier, J. Monnot, and V. Th. Paschos, “Reoptimization of minimum and maximum traveling salesman’s tours,” in: Proc. SWAT 2006; LNCS, 4059, 196–207, Springer, Berlin (2006).
H. J. Bockenhauer, L. Forlizzi, J. Hromkovic, et al., “On the approximability of TSP on local modifications of optimal solved instances,” Algorithmic Oper. Res., 2(2), 83–93 (2007).
H. J. Bockenhauer, J. Hromkovic, T. Momke, and P. Widmayer, “On the hardness of reoptimization,” in: Proc. 34th Intern. Conf. on Current Trends in Theory and Practice of Computer Science (SOF-SEM 2008); LNCS, 4910, 50–65, Springer, Berlin (2008)
B. Escoffier, M. Milanic, and V. Th. Paschos, “Simple and fast reoptimizations for the Steiner tree problem,” Algorithmic Oper. Res., 4(2), 86–94 (2009).
C. Archetti, L. Bertazzi, and M. G. Speranza, “Reoptimizing the traveling salesman problem,” Networks, 42(3), 154–159 (2003).
C. Archetti, L. Bertazzi, and M. G. Speranza, “Reoptimizing the 0-1 knapsack problem,” Manuscript (2008).
G. Ausiello, V. Bonifaci, and B. Escoffier, “Complexity and approximation in reoptimization,” in: Computability in Context: Computation and Logic in the Real World, Computability in Europe (CiE) Conference 2007 (June, 2007), Imperial College Press (2010), pp. 24–33.
V. A. Chvatal, “A greedy heuristic for the set covering problem,” Math. Oper. Res., 4, No. 3, 233–235 (1979).
Author information
Authors and Affiliations
Corresponding author
Additional information
Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 27–31, November–December 2010.
Rights and permissions
About this article
Cite this article
Mikhailyuk, V.A. Reoptimization of set covering problems. Cybern Syst Anal 46, 879–883 (2010). https://doi.org/10.1007/s10559-010-9269-z
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10559-010-9269-z