Smoothed analysis: an attempt to explain the behavior of algorithms in practice
DA Spielman, SH Teng - Communications of the ACM, 2009 - dl.acm.org
ACM: Digital Library: Communications of the ACM ACM Digital Library Communications of the
ACM Volume 52, Number 10 (2009), Pages 76-84 Smoothed analysis: an attempt to explain …
ACM Volume 52, Number 10 (2009), Pages 76-84 Smoothed analysis: an attempt to explain …
The smoothed analysis of algorithms
DA Spielman - … of Computation Theory: 15th International Symposium …, 2005 - Springer
LNCS 3623 - The Smoothed Analysis of Algorithms Page 1 The Smoothed Analysis of Algorithms
Daniel A. Spielman Department of Mathematics, Massachusetts Institute of Technology …
Daniel A. Spielman Department of Mathematics, Massachusetts Institute of Technology …
On Bayes risk lower bounds
This paper provides a general technique for lower bounding the Bayes risk of statistical
estimation, applicable to arbitrary loss functions and arbitrary prior distributions. A lower …
estimation, applicable to arbitrary loss functions and arbitrary prior distributions. A lower …
[图书][B] Algorithm Engineering
M Müller-Hannemann, S Schirra - 2001 - Springer
The systematic development of efficient algorithms has become a key technology for all
kinds of ambitious and innovative computer applications. With major parts of algorithmic …
kinds of ambitious and innovative computer applications. With major parts of algorithmic …
On the integrality gap of binary integer programs with gaussian data
For a binary integer program (IP) max c T x, A x≤ b, x∈{0, 1} n, where A∈ R m× n and c∈ R
n have independent Gaussian entries and the right-hand side b∈ R m satisfies that its …
n have independent Gaussian entries and the right-hand side b∈ R m satisfies that its …
Settling the complexity of local max-cut (almost) completely
R Elsässer, T Tscheuschner - International Colloquium on Automata …, 2011 - Springer
We consider the problem of finding a local optimum for the Max-Cut problem with FLIP-
neighborhood, in which exactly one node changes the partition. Schäffer and Yannakakis …
neighborhood, in which exactly one node changes the partition. Schäffer and Yannakakis …
Smoothed efficient algorithms and reductions for network coordination games
Worst-case hardness results for most equilibrium computation problems have raised the
need for beyond-worst-case analysis. To this end, we study the smoothed complexity of …
need for beyond-worst-case analysis. To this end, we study the smoothed complexity of …
Basis reduction and the complexity of branch-and-bound
The classical branch-and-bound algorithm for the integer feasibility problem has exponential
worst case complexity. We prove that it is surprisingly efficient on reformulations of (0.1), in …
worst case complexity. We prove that it is surprisingly efficient on reformulations of (0.1), in …
Smoothed analysis: analysis of algorithms beyond worst case
Viele Algorithmen sind in der Praxis effizient, obwohl ihre Laufzeit im Worst Case sehr
schlecht ist. Der Grund für diese Diskrepanz ist, dass die reine Betrachtung des Worst Case …
schlecht ist. Der Grund für diese Diskrepanz ist, dass die reine Betrachtung des Worst Case …
Integrality gaps for random integer programs via discrepancy
In this work, we prove new bounds on the additive gap between the value of a random
integer program max c T x, Ax≤ b, x∈{0, 1} n with m constraints and that of its linear …
integer program max c T x, Ax≤ b, x∈{0, 1} n with m constraints and that of its linear …