Search results for "smoothed analysis"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
3	Daniel A. Spielman, Shang-Hua Teng	Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time.	J. ACM	2004	DBLP DOI BibTeX RDF	complexity, perturbation, Simplex method, smoothed analysis
2	Peter Bürgisser, Felipe Cucker	Solving polynomial equations in smoothed polynomial time and a near solution to smale's 17th problem.	STOC	2010	DBLP DOI BibTeX RDF	approximate zero, polynomial equation solving, complexity, polynomial time, smoothed analysis, homotopy methods
2	Bodo Manthey, Heiko Röglin	Improved smoothed analysis of the k-means method.	SODA	2009	DBLP DOI BibTeX RDF
2	Tobias Friedrich, Thomas Sauerwald, Dan Vilenchik	Smoothed Analysis of Balancing Networks.	ICALP	2009	DBLP DOI BibTeX RDF
2	Mahmoud Fouz, Manfred Kufleitner, Bodo Manthey, Nima Zeini Jahromi	On Smoothed Analysis of Quicksort and Hoare's Find.	COCOON	2009	DBLP DOI BibTeX RDF
2	Heiko Röglin, Shang-Hua Teng	Smoothed Analysis of Multiobjective Optimization.	FOCS	2009	DBLP DOI BibTeX RDF	multiobjective optimization, Pareto-optimal solutions, smoothed analysis
2	Adam Tauman Kalai, Alex Samorodnitsky, Shang-Hua Teng	Learning and Smoothed Analysis.	FOCS	2009	DBLP DOI BibTeX RDF	Computational Learning Theory, Smoothed Analysis
2	Bodo Manthey, Heiko Röglin	Worst-Case and Smoothed Analysis of k-Means Clustering with Bregman Divergences.	ISAAC	2009	DBLP DOI BibTeX RDF
2	Heiko Röglin, Berthold Vöcking	Smoothed analysis of integer programming.	Math. Program.	2007	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 68Q25, 90C27, 90C10
2	Daniel A. Spielman	The Smoothed Analysis of Algorithms.	FCT	2005	DBLP DOI BibTeX RDF
2	Heiko Röglin, Berthold Vöcking	Smoothed Analysis of Integer Programming.	IPCO	2005	DBLP DOI BibTeX RDF
2	Shang-Hua Teng	Smoothed Analysis of Algorithms and Heuristics.	COCOON	2005	DBLP DOI BibTeX RDF
2	René Beier, Berthold Vöcking	Typical properties of winners and losers in discrete optimization.	STOC	2004	DBLP DOI BibTeX RDF	optimization problems, average-case analysis, smoothed analysis
2	Cyril Banderier, René Beier, Kurt Mehlhorn	Smoothed Analysis of Three Combinatorial Problems.	MFCS	2003	DBLP DOI BibTeX RDF
2	Daniel A. Spielman, Shang-Hua Teng	Smoothed Analysis (Motivation and Discrete Models).	WADS	2003	DBLP DOI BibTeX RDF
2	Daniel A. Spielman, Shang-Hua Teng	Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time.	STOC	2001	DBLP DOI BibTeX RDF
1	Mahmoud Fouz, Manfred Kufleitner, Bodo Manthey, Nima Zeini Jahromi	On Smoothed Analysis of Quicksort and Hoare's Find.	Algorithmica	2012	DBLP DOI BibTeX RDF
1	Peter Bürgisser, Dennis Amelunxen	Robust smoothed analysis of a condition number for linear programming.	Math. Program.	2012	DBLP DOI BibTeX RDF
1	Tobias Brunsch, Heiko Röglin	Improved smoothed analysis of multiobjective optimization.	STOC	2012	DBLP DOI BibTeX RDF
1	Tobias Friedrich, Thomas Sauerwald, Dan Vilenchik	Smoothed analysis of balancing networks.	Random Struct. Algorithms	2011	DBLP DOI BibTeX RDF
1	David Arthur, Bodo Manthey, Heiko Röglin	Smoothed Analysis of the k-Means Method.	J. ACM	2011	DBLP DOI BibTeX RDF
1	Tobias Brunsch, Heiko Röglin	Improved Smoothed Analysis of Multiobjective Optimization	CoRR	2011	DBLP BibTeX RDF
1	John Dunagan, Daniel A. Spielman, Shang-Hua Teng	Smoothed analysis of condition numbers and complexity implications for linear programming.	Math. Program.	2011	DBLP DOI BibTeX RDF
1	Bodo Manthey, Heiko Röglin	Smoothed Analysis: Analysis of Algorithms Beyond Worst Case.	it - Information Technology	2011	DBLP DOI BibTeX RDF
1	Endre Boros, Khaled M. Elbassioni, Mahmoud Fouz, Vladimir Gurvich, Kazuhisa Makino, Bodo Manthey	Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes.	ICALP	2011	DBLP DOI BibTeX RDF
1	André Berger, Heiko Röglin, Ruben van der Zwaan	Path Trading: Fast Algorithms, Smoothed Analysis, and Hardness Results.	SEA	2011	DBLP DOI BibTeX RDF
1	Markus Bläser, Bodo Manthey, B. V. Raghavendra Rao	Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals.	WADS	2011	DBLP DOI BibTeX RDF
1	Felipe Cucker, Raphael Hauser, Martin Lotz	Adversarial smoothed analysis.	J. Complexity	2010	DBLP DOI BibTeX RDF
1	Tobias Friedrich, Thomas Sauerwald, Dan Vilenchik	Smoothed Analysis of Balancing Networks	CoRR	2010	DBLP BibTeX RDF
1	Peter Bürgisser, Felipe Cucker	Smoothed Analysis of Moore-Penrose Inversion.	SIAM J. Matrix Analysis Applications	2010	DBLP DOI BibTeX RDF
1	Mihailo Stojnic	A smoothed analysis approach to l1 optimization in compressed sensing.	ICASSP	2010	DBLP DOI BibTeX RDF
1	Daniel A. Spielman, Shang-Hua Teng	Smoothed analysis: an attempt to explain the behavior of algorithms in practice.	Commun. ACM	2009	DBLP DOI BibTeX RDF
1	Felipe Cucker, Teresa Krick, Gregorio Malajovich, Mario Wschebor	A Numerical Algorithm for Zero Counting. II: Distance to Ill-posedness and Smoothed Analysis	CoRR	2009	DBLP BibTeX RDF
1	Mahmoud Fouz, Manfred Kufleitner, Bodo Manthey, Nima Zeini Jahromi	On Smoothed Analysis of Quicksort and Hoare's Find	CoRR	2009	DBLP BibTeX RDF
1	Siddhartha Chaudhuri, Vladlen Koltun	Smoothed analysis of probabilistic roadmaps.	Comput. Geom.	2009	DBLP DOI BibTeX RDF
1	David Arthur, Sergei Vassilvitskii	Worst-Case and Smoothed Analysis of the ICP Algorithm, with an Application to the k-Means Method.	SIAM J. Comput.	2009	DBLP DOI BibTeX RDF
1	Mark de Berg, Herman J. Haverkort, Constantinos P. Tsirogiannis	Visibility maps of realistic terrains have linear smoothed complexity.	Symposium on Computational Geometry	2009	DBLP DOI BibTeX RDF	realistic input, terrains, smoothed analysis, visibility maps
1	Xi Chen, Xiaotie Deng, Shang-Hua Teng	Settling the complexity of computing two-player Nash equilibria.	J. ACM	2009	DBLP DOI BibTeX RDF	Arrow-Debreu market, Brouwer's fixed point, Lemke-Howson algorithm, PPAD-completeness, Sperner's lemma, Nash equilibrium, smoothed analysis, Two-player game
1	David Arthur, Bodo Manthey, Heiko Röglin	k-Means Has Polynomial Smoothed Complexity.	FOCS	2009	DBLP DOI BibTeX RDF	clustering, k-means, smoothed analysis
1	Bodo Manthey, Heiko Röglin	Improved Smoothed Analysis of the k-Means Method	CoRR	2008	DBLP BibTeX RDF
1	Adam Tauman Kalai, Shang-Hua Teng	Decision trees are PAC-learnable from most product distributions: a smoothed analysis	CoRR	2008	DBLP BibTeX RDF
1	Bodo Manthey, Till Tantau	Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise.	MFCS	2008	DBLP DOI BibTeX RDF
1	Bin Ma	Why Greed Works for Shortest Common Superstring Problem.	CPM	2008	DBLP DOI BibTeX RDF
1	Christine Chung, Katrina Ligett, Kirk Pruhs, Aaron Roth	The Price of Stochastic Anarchy.	SAGT	2008	DBLP DOI BibTeX RDF
1	Bodo Manthey, Till Tantau	Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise.	Electronic Colloquium on Computational Complexity (ECCC)	2007	DBLP BibTeX RDF
1	Bodo Manthey, Rüdiger Reischuk	Smoothed analysis of binary search trees.	Theor. Comput. Sci.	2007	DBLP DOI BibTeX RDF
1	Shang-Hua Teng	Game and Market Equilibria: Computation, Approximation, and Smoothed Analysis.	AAIM	2007	DBLP DOI BibTeX RDF
1	Bodo Manthey, Till Tantau	Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise.	Probabilistic Methods in the Design and Analysis of Algorithms	2007	DBLP BibTeX RDF
1	Matthias Englert, Heiko Röglin, Berthold Vöcking	Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP: extended abstract.	SODA	2007	DBLP DOI BibTeX RDF
1	Jonathan A. Kelner, Evdokia Nikolova	On the Hardness and Smoothed Complexity of Quasi-Concave Minimization.	FOCS	2007	DBLP DOI BibTeX RDF
1	René Beier, Heiko Röglin, Berthold Vöcking	The Smoothed Number of Pareto Optimal Solutions in Bicriteria Integer Optimization.	IPCO	2007	DBLP DOI BibTeX RDF
1	Michael Krivelevich, Benny Sudakov, Prasad Tetali	On smoothed analysis in dense graphs and formulas.	Random Struct. Algorithms	2006	DBLP DOI BibTeX RDF
1	Arvind Sankar, Daniel A. Spielman, Shang-Hua Teng	Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices.	SIAM J. Matrix Analysis Applications	2006	DBLP DOI BibTeX RDF
1	David Arthur, Sergei Vassilvitskii	Worst-case and Smoothed Analysis of the ICP Algorithm, with an Application to the k-means Method.	FOCS	2006	DBLP DOI BibTeX RDF
1	Xi Chen, Xiaotie Deng, Shang-Hua Teng	Computing Nash Equilibria: Approximation and Smoothed Complexity.	FOCS	2006	DBLP DOI BibTeX RDF
1	Roman Vershynin	Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method.	FOCS	2006	DBLP DOI BibTeX RDF
1	Bodo Manthey, Rüdiger Reischuk	Smoothed Analysis of the Height of Binary Search Trees	Electronic Colloquium on Computational Complexity (ECCC)	2005	DBLP BibTeX RDF
1	Bodo Manthey	Approximability of cycle covers and smoothed analysis of binary search trees.		2005	RDF
1	Amit Deshpande, Daniel A. Spielman	Improved Smoothed Analysis of the Shadow Vertex Simplex Method.	FOCS	2005	DBLP DOI BibTeX RDF
1	Bodo Manthey, Rüdiger Reischuk	Smoothed Analysis of Binary Search Trees.	ISAAC	2005	DBLP DOI BibTeX RDF
1	Uriel Feige	Rigorous analysis of heuristics for NP-hard problems.	SODA	2005	DBLP DOI BibTeX RDF
1	Heiner Ackermann, Alantha Newman, Heiko Röglin, Berthold Vöcking	Decision Making Based on Approximate and Smoothed Pareto Curves.	ISAAC	2005	DBLP DOI BibTeX RDF
1	Mario Wschebor	Smoothed analysis of kappa(A).	J. Complexity	2004	DBLP DOI BibTeX RDF
1	Abraham Flaxman, Alan M. Frieze	The Diameter of Randomly Perturbed Digraphs and Some Applications..	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	John Dunagan, Daniel A. Spielman, Shang-Hua Teng	Smoothed Analysis of Interior-Point Algorithms: Condition Number	CoRR	2003	DBLP BibTeX RDF
1	Arvind Sankar, Daniel A. Spielman, Shang-Hua Teng	Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices	CoRR	2003	DBLP BibTeX RDF
1	Daniel A. Spielman, Shang-Hua Teng	Smoothed Analysis of Interior-Point Algorithms: Termination	CoRR	2003	DBLP BibTeX RDF
1	Daniel A. Spielman, Shang-Hua Teng	Smoothed analysis of termination of linear programming algorithms.	Math. Program.	2003	DBLP DOI BibTeX RDF
1	Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela, Guido Schäfer, Tjark Vredeveld	Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm.	FOCS	2003	DBLP DOI BibTeX RDF
1	Valentina Damerow, Friedhelm Meyer auf der Heide, Harald Räcke, Christian Scheideler, Christian Sohler	Smoothed Motion Complexity.	ESA	2003	DBLP DOI BibTeX RDF
1	Avrim Blum, John Dunagan	Smoothed analysis of the perceptron algorithm for linear programming.	SODA	2002	DBLP DOI BibTeX RDF
1	Daniel A. Spielman, Shang-Hua Teng	Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time	CoRR	2001	DBLP BibTeX RDF