Abstract
We consider the smoothed analysis of Euclidean optimization problems. Here, input points are sampled according to density functions that are bounded by a sufficiently small smoothness parameter φ. For such inputs, we provide a general and systematic approach that allows to design linear-time approximation algorithms whose output is asymptotically optimal, both in expectation and with high probability.
Applications of our framework include maximum matching, maximum TSP, and the classical problems of k-means clustering and bin packing. Apart from generalizing corresponding average-case analyses, our results extend and simplify a polynomial-time probable approximation scheme on multidimensional bin packing on φ-smooth instances, where φ is constant (Karger and Onak, SODA 2007).
Both techniques and applications of our rounding-based approach are orthogonal to the only other framework for smoothed analysis on Euclidean problems we are aware of (Bläser et al., Algorithmica 2012).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Approximation Scheme
- Approximation Ratio
- Maximum Match
- Quantization Framework
- Polynomial Approximation Scheme
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Anstee, R.P.: A polynomial algorithm for b-matchings: An alternative approach. Information Processing Letters 24(3), 153–157 (1987)
Arthur, D., Manthey, B., Röglin, H.: Smoothed analysis of the k-means method. Journal of the ACM 58(5), 19:1–19:31 (2011)
Arthur, D., Vassilvitskii, S.: Worst-case and smoothed analysis of the ICP algorithm, with an application to the k-means method. SIAM Journal on Computing 39(2), 766–782 (2009)
Avis, D.: A survey of heuristics for the weighted matching problem. Networks 13(4), 475–493 (1983)
Awasthi, P., Blum, A., Sheffet, O.: Center-based clustering under perturbation stability. Information Processing Letters 112(1-2), 49–54 (2012)
Bansal, N., Correa, J.É.R., Kenyon, C., Sviridenko, M.: Bin packing in multiple dimensions: Inapproximability results and approximation schemes. Mathematics of Operations Research 31, 31–49 (2006)
Barvinok, A., Fekete, S.P., Johnson, D.S., Tamir, A., Woeginger, G.J., Woodroofe, R.: The geometric maximum traveling salesman problem. J. ACM 50(5), 641–664 (2003)
Barvinok, A.I.: Two algorithmic results for the traveling salesman problem. Mathematics of Operations Research 21(1), 65–84 (1996)
Beier, R., Vöcking, B.: Typical properties of winners and losers in discrete optimization. SIAM Journal on Computing 35(4), 855–881 (2006)
Bläser, M., Manthey, B., Raghavendra Rao, B.V.: Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals. Algorithmica 66(2), 397–418 (2013)
Boros, E., Elbassioni, K., Fouz, M., Gurvich, V., Makino, K., Manthey, B.: Stochastic mean payoff games: Smoothed analysis and approximation schemes. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol. 6755, pp. 147–158. Springer, Heidelberg (2011)
Chen, K.: On coresets for k-median and k-means clustering in metric and euclidean spaces and their applications. SIAM Journal on Computing 39(3), 923–947 (2009)
Dasgupta, S.: The hardness of k-means clustering. Technical report cs2007-0890, University of California, San Diego (2007)
Dyer, M.E., Frieze, A.M., McDiarmid, C.J.H.: Partitioning heuristics for two geometric maximization problems. Operations Research Letters 3(5), 267–270 (1984)
Englert, M., Röglin, H., Vöcking, B.: Worst case and probabilistic analysis of the 2-opt algorithm for the TSP: Extended abstract. In: 18th Ann. ACM-SIAM Symp. on Discrete Algorithms, SODA 2007, pp. 1295–1304. SIAM (2007)
Fekete, S.P., Meijer, H., Rohe, A., Tietze, W.: Solving a ”hard” problem to approximate an ”easy” one: Heuristics for maximum matchings and maximum traveling salesman problems. ACM J. on Experimental Algorithmics. 7, 11 (2002)
Feldman, D., Monemizadeh, M., Sohler, C.: A PTAS for k-means clustering based on weak coresets. In: 23rd Ann. Symp. on Computational Geometry, SCG 2007, pp. 11–18. ACM (2007)
Fernandez de la Vega, W., Lueker, G.: Bin packing can be solved within 1 + ε in linear time. Combinatorica 1(4), 349–355 (1981)
Gabow, H.N.: An efficient implementation of Edmonds’ algorithm for maximum matching on graphs. Journal of the ACM 23(2), 221–234 (1976)
Har-Peled, S., Mazumdar, S.: On coresets for k-means and k-median clustering. In: 36th Ann. ACM Symp. on Theory of Computing, STOC 2004, pp. 291–300 (2004)
Inaba, M., Katoh, N., Imai, H.: Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering (extended abstract). In: 10th Annual Symp. on Computational Geometry, SCG 1994, pp. 332–339 (1994)
Karger, D., Onak, K.: Polynomial approximation schemes for smoothed and random instances of multidimensional packing problems. In: 18th Ann. ACM-SIAM Symp. on Discrete Algorithms, SODA 2007, pp. 1207–1216 (2007)
Karp, R.M., Luby, M., Marchetti-Spaccamela, A.: A probabilistic analysis of multidimensional bin packing problems. In: 16th Annual ACM Symp. on Theory of Computing, STOC 1984, pp. 289–298. ACM, New York (1984)
Mahajan, M., Nimbhorkar, P., Varadarajan, K.: The planar k-means problem is NP-hard. Theoretical Computer Science 442, 13–21 (2012)
Plotkin, S.A., Shmoys, D.B., Tardos, É.: Fast approximation algorithms for fractional packing and covering problems. Mathematics of Operations Research 20(2), 257 (1995)
Spielman, D.A., Teng, S.-H.: Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM 51(3), 385–463 (2004)
Steele, J.M.: Subadditive Euclidean functionals and nonlinear growth in geometric probability. The Annals of Probability 9(3), 365–376 (1981)
Weber, M., Liebling, T.M.: Euclidean matching problems and the metropolis algorithm. Mathematical Methods of Operations Research 30(3), A85–A110 (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Curticapean, R., Künnemann, M. (2013). A Quantization Framework for Smoothed Analysis of Euclidean Optimization Problems. In: Bodlaender, H.L., Italiano, G.F. (eds) Algorithms – ESA 2013. ESA 2013. Lecture Notes in Computer Science, vol 8125. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40450-4_30
Download citation
DOI: https://doi.org/10.1007/978-3-642-40450-4_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40449-8
Online ISBN: 978-3-642-40450-4
eBook Packages: Computer ScienceComputer Science (R0)