Abstract
While the complexity of min-max and min-max regret versions of most classical combinatorial optimization problems has been thoroughly investigated, there are very few studies about their approximation. For a bounded number of scenarios, we establish a general approximation scheme which can be used for min-max and min-max regret versions of some polynomial problems. Applying this scheme to shortest path and minimum spanning tree, we obtain fully polynomial-time approximation schemes with much better running times than the ones previously presented in the literature.
This work has been partially funded by grant CNRS/CGRI-FNRS number 18227. The second author was partially supported by the ACI Sécurité Informatique grant-TADORNE project 2004.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Aho, A.V., Hopcroft, J.E., Ullmann, J.D.: The design and analysis of computer algorithms. Addison-Wesley, Reading (1976)
Aissi, H., Bazgan, C., Vanderpooten, D.: Approximation complexity of min-max (regret) versions of shortest path, spanning tree, and knapsack. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 862–873. Springer, Heidelberg (2005)
Barahona, F., Pulleyblank, R.: Exact arborescences, matching and cycles. Discrete Applied Mathematics 16, 91–99 (1987)
Edmonds, J.: System of distinct representatives and linear algebra. Journal of Research of the National Bureau of Standards 71, 241–245 (1967)
Hong, S.P., Chung, S.J., Park, B.H.: A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem. Operations Research Letters 32(3), 233–239 (2004)
Kouvelis, P., Yu, G.: Robust discrete optimization and its applications. Kluwer Academic Publishers, Boston (1997)
Mahajan, M., Vinay, V.: A combinatorial algorithm for the determinant. In: Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1997), New Orleans, USA, pp. 730–738 (1997)
Papadimitriou, C.H.: Computational complexity. Addison Wesley, Reading (1994)
Papadimitriou, C.H., Yannakakis, M.: On the approximability of trade-offs and optimal access of web sources. In: IEEE Symposium on Foundations of Computer Science (FOCS 2000), Redondo Beach, California, USA, pp. 86–92 (2000)
Tutte, W.T.: Graph Theory. Encyclopedia of Mathematics and its Applications, vol. 21. Addison-Wesley, Reading (1984)
Warburton, A.: Approximation of Pareto optima in multiple-objective, shortest-path problems. Operations Research 35, 70–79 (1987)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Aissi, H., Bazgan, C., Vanderpooten, D. (2006). Approximating Min-Max (Regret) Versions of Some Polynomial Problems. In: Chen, D.Z., Lee, D.T. (eds) Computing and Combinatorics. COCOON 2006. Lecture Notes in Computer Science, vol 4112. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11809678_45
Download citation
DOI: https://doi.org/10.1007/11809678_45
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-36925-7
Online ISBN: 978-3-540-36926-4
eBook Packages: Computer ScienceComputer Science (R0)