Abstract | ||
---|---|---|
We prove novel algorithmic guarantees for several online problems in the smoothed analysis model. In this model, at each time step an adversary chooses an input distribution with density function bounded above pointwise by a multiplicative factor from the uniform distribution; nature then samples an input from this distribution. This interpolates between the extremes of worst-case and average case... |
Year | DOI | Venue |
---|---|---|
2021 | 10.1109/FOCS52979.2021.00095 | 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) |
Keywords | DocType | ISSN |
Computer science,Analytical models,Adaptation models,Density functional theory,Standards,Optimization,Dispersion | Conference | 0272-5428 |
ISBN | Citations | PageRank |
978-1-6654-2055-6 | 0 | 0.34 |
References | Authors | |
0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Nika Haghtalab | 1 | 0 | 0.34 |
Tim Roughgarden | 2 | 4177 | 353.32 |
Abhishek Shetty | 3 | 0 | 0.34 |