×

Reoptimization of weighted graph and covering problems. (English) Zbl 1209.68632

Bampis, Evripidis (ed.) et al., Approximation and online algorithms. 6th international workshop, WAOA 2008, Karlsruhe, Germany, September 18–19, 2008. Revised papers. Berlin: Springer (ISBN 978-3-540-93979-5/pbk). Lecture Notes in Computer Science 5426, 201-213 (2009).
Summary: Given an instance of an optimization problem and a good solution of that instance, the reoptimization is a concept of analyzing how does the solution change when the instance is locally modified. We investigate reoptimization of the following problems: Maximum Weighted Independent Set, Maximum Weighted Clique, Minimum Weighted Dominating Set, Minimum Weighted Set Cover and Minimum Weighted Vertex Cover. The local modifications we consider are addition or removal of a constant number of edges to the graph, or elements to the covering sets in case of Set Cover problem. We present the following results:
1. We provide a PTAS for reoptimization of the unweighted versions of the aforementioned problems when the input solution is optimal.
2. We provide two general techniques for analyzing approximation ratio of the weighted reoptimization problems.
3. We apply our techniques to reoptimization of the considered optimization problems and obtain tight approximation ratios in all the cases.
For the entire collection see [Zbl 1155.68005].

MSC:

68W25 Approximation algorithms
90C35 Programming involving graphs or networks
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Archetti, C., Bertazzi, L., Speranza, M.G.: Reoptimizing the traveling salesman problem. Networks 42(3), 154–159 (2003) · Zbl 1053.90126 · doi:10.1002/net.10091
[2] Ausiello, G., Escoffier, B., Monnot, J., Paschos, V.T.: Reoptimization of minimum and maximum traveling salesman’s tours. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, vol. 4059, pp. 196–207. Springer, Heidelberg (2006) · Zbl 1141.90506 · doi:10.1007/11785293_20
[3] Bar-Yehuda, R., Even, S.: A local-ratio theorem for approximating the weighted vertex cover problem. Annals of Discrete Mathematics 25, 27–46 (1985) · Zbl 0545.90074
[4] Bilò, D., Böckenhauer, H.-J., Hromkovič, J., Královič, R., Mömke, T., Widmayer, P., Zych, A.: Reoptimization of steiner trees. In: Gudmundsson, J. (ed.) SWAT 2008. LNCS, vol. 5124, pp. 258–269. Springer, Heidelberg (2008) · Zbl 1155.68574 · doi:10.1007/978-3-540-69903-3_24
[5] Böckenhauer, H.-J., Forlizzi, L., Hromkovič, J., Kneis, J., Kupke, J., Proietti, G., Widmayer, P.: Reusing optimal TSP solutions for locally modified input instances (extended abstract). In: Fourth IFIP International Conference on Theoretical Computer Science–TCS 2006. IFIP Int. Fed. Inf. Process, vol. 209, pp. 251–270. Springer, New York (2006) · doi:10.1007/978-0-387-34735-6_21
[6] Böckenhauer, H.-J., Hromkovic, J., Mömke, T., Widmayer, P.: On the hardness of reoptimization. In: Geffert, V., Karhumäki, J., Bertoni, A., Preneel, B., Návrat, P., Bieliková, M. (eds.) SOFSEM 2008. LNCS, vol. 4910, pp. 50–65. Springer, Heidelberg (2008) · Zbl 1133.68351 · doi:10.1007/978-3-540-77566-9_5
[7] Boppana, R., Halldórsson, M.M.: Approximating maximum independent sets by excluding subgraphs. BIT 32(2), 180–196 (1992) · Zbl 0761.68044 · doi:10.1007/BF01994876
[8] Escoffier, B., Milanic, M., Paschos, V.T.: Simple and fast reoptimizations for the Steiner tree problem. Technical Report 2007-01, DIMACS (2007)
[9] Hastad, J.: Clique is hard to approximate within n 1-{\(\epsilon\)} . In: Foundations of Computer Science -FOCS 1996, pp. 627–636 (1996)
[10] Hastad, J.: Some optimal inapproximability results. In: STOC 1997: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pp. 1–10. ACM, New York (1997) · doi:10.1145/258533.258536
[11] Johnson, D.S.: Approximation algorithms for combinatorial problems. In: STOC 1973: Proceedings of the fifth annual ACM symposium on Theory of computing, pp. 38–49. ACM, New York (1973) · doi:10.1145/800125.804034
[12] Monien, B., Speckenmeyer, E.: Ramsey numbers and an approximation algorithm for the vertex cover problem. Acta Inf. 22(1), 115–123 (1985) · Zbl 0558.05044 · doi:10.1007/BF00290149
[13] Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability pcp characterization of np. In: STOC 1997: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pp. 475–484. ACM, New York (1997) · Zbl 0963.68175 · doi:10.1145/258533.258641
[14] Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: STOC 2006: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pp. 681–690. ACM, New York (2006) · Zbl 1301.68152 · doi:10.1145/1132516.1132612
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.