Cover Image

Optimal Smoothed Analysis of the Simplex Method

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bach, Eleon, Huiberts, Sophie
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Beyond Smoothed Analysis: Analyzing the Simplex Method by the Book
by: Bach, Eleon, et al.
Published: (2025)

Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method
by: Huiberts, Sophie, et al.
Published: (2022)

An unconditional lower bound for the active-set method in convex quadratic maximization
by: Bach, Eleon, et al.
Published: (2025)

A nearly optimal randomized algorithm for explorable heap selection
by: Borst, Sander, et al.
Published: (2022)

Smoothed Analysis of Online Metric Problems
by: Coester, Christian, et al.
Published: (2025)

Smoothed Analysis of Dynamic Graph Algorithms
by: Meir, Uri, et al.
Published: (2025)

Smoothed Analysis of the k-Swap Neighborhood for Makespan Scheduling
by: Rohwedder, Lars, et al.
Published: (2024)

Interior point methods are not worse than Simplex
by: Allamigeon, Xavier, et al.
Published: (2022)

Hardness and Approximability of Dimension Reduction on the Probability Simplex
by: Bruno, Roberto
Published: (2024)

Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion
by: Li, Yingxi, et al.
Published: (2025)

New Tools for Smoothed Analysis: Least Singular Value Bounds for Random Matrices with Dependent Entries
by: Bhaskara, Aditya, et al.
Published: (2024)

Time-Optimal Directed q-Analysis
by: Windisch, Felix, et al.
Published: (2025)

Optimal Approximation -- Smoothness Tradeoffs for Soft-Max Functions
by: Epasto, Alessandro, et al.
Published: (2020)

Bounding the Optimal Performance of Online Randomized Primal-Dual Methods
by: Xu, Pan
Published: (2025)

Differentially Private Selection using Smooth Sensitivity
by: Yamamoto, Akito, et al.
Published: (2024)

Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search
by: Benomar, Ziyad, et al.
Published: (2025)

Worst-Case and Smoothed Analysis of the Hartigan-Wong Method for k-Means Clustering
by: Manthey, Bodo, et al.
Published: (2023)

A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations
by: Charikar, Moses, et al.
Published: (2024)

A Global Analysis of the Primal-Dual Method for Pliable Families
by: Bansal, Ishan
Published: (2023)

Optimal Extended Formulations from Optimal Dynamic Programming Algorithms
by: Oliveira, Mateus de Oliveira, et al.
Published: (2026)

Online Metric Matching: Beyond the Worst Case
by: Yang, Mingwei, et al.
Published: (2024)

Fingerprint Filters Are Optimal
by: Kuszmaul, William, et al.
Published: (2025)

Optimal antimatroid sorting
by: Berendsohn, Benjamin Aram
Published: (2025)

Color Fault-Tolerant Distance Preservers: Õptimal Size in Conditionally Õptimal Time
by: Parter, Merav, et al.
Published: (2025)

Optimal Decentralized Smoothed Online Convex Optimization
by: Bhuyan, Neelkamal, et al.
Published: (2024)

Time-Optimal $k$-Server
by: Frei, Fabian, et al.
Published: (2025)

The Role of Commitment in Optimal Stopping
by: Correa, José, et al.
Published: (2025)

Simpler Universally Optimal Dijkstra
by: van der Hoog, Ivor, et al.
Published: (2025)

Nearly Optimal List Labeling
by: Bender, Michael A., et al.
Published: (2024)

Optimal Non-Oblivious Open Addressing
by: Bender, Michael A., et al.
Published: (2025)

Instance-Optimality in PageRank Computation
by: Thorup, Mikkel, et al.
Published: (2025)

Optimal Static Fully Indexable Dictionaries
by: Liang, Jingxun, et al.
Published: (2025)

Maximal Palindromes in MPC: Simple and Optimal
by: Pissis, Solon P.
Published: (2025)

Static Retrieval Revisited: To Optimality and Beyond
by: Hu, Yang, et al.
Published: (2025)

Optimal $k$-Secretary with Logarithmic Memory
by: Qiao, Mingda, et al.
Published: (2025)

Optimal Stopping with a Predicted Prior
by: Bai, Tian, et al.
Published: (2025)

Nearly Optimal Internal Dictionary Matching
by: Chen, Jingbang, et al.
Published: (2023)

Expander Decomposition with Almost Optimal Overhead
by: Bansal, Nikhil, et al.
Published: (2026)

An Optimal Algorithm for Stochastic Vertex Cover
by: Brand, Jan van den, et al.
Published: (2026)

Engineering Optimal Parallel Task Scheduling
by: Akram, Matthew, et al.
Published: (2024)