Copertina

The Competition Complexity of Prophet Inequalities

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Brustle, Johannes, Correa, José, Dütting, Paul, Ezra, Tomer, Feldman, Michal, Verdugo, Victor
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Computer Science and Game Theory Data Structures and Algorithms 90C59, 68W27, 62L15, 60G40
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Prophet Inequality with Conservative Prediction
di: Brüstle, Johannes, et al.
Pubblicazione: (2026)

Residual Prophet Inequalities
di: Correa, Jose, et al.
Pubblicazione: (2025)

A Speed-up for Helsgaun's TSP Heuristic by Relaxing the Positive Gain Criterion
di: Ammann, Sabrina C. L., et al.
Pubblicazione: (2024)

A $5$-Approximation Analysis for the Cover Small Cuts Problem
di: Simmons, Miles, et al.
Pubblicazione: (2026)

Improved Approximation Algorithms for Capacitated Network Design and Flexible Graph Connectivity
di: Bansal, Ishan, et al.
Pubblicazione: (2024)

On the Advice Complexity of Online Unit Clustering
di: Nagy-György, Judit
Pubblicazione: (2023)

Optimal Online Bipartite Matching in Degree-2 Graphs
di: Bhangale, Amey, et al.
Pubblicazione: (2025)

Building a Nest by an Automaton
di: Czyzowicz, Jurek, et al.
Pubblicazione: (2019)

Loss Minimization for Electrical Flows over Spanning Trees on Grids
di: Ito, Takehiro, et al.
Pubblicazione: (2024)

New Theoretical Insights and Algorithmic Solutions for Reconstructing Score Sequences from Tournament Score Sets
di: Liu, Bowen
Pubblicazione: (2025)

Near-Optimal Relative Error Streaming Quantile Estimation via Elastic Compactors
di: Gribelyuk, Elena, et al.
Pubblicazione: (2024)

Efficient Processing of Subsequent Densest Subgraph Query
di: Hung, Chia-Yang, et al.
Pubblicazione: (2024)

Deterministic Algorithm and Faster Algorithm for Submodular Maximization subject to a Matroid Constraint
di: Buchbinder, Niv, et al.
Pubblicazione: (2024)

A simple Path-based LP Relaxation for Directed Steiner Tree
di: Pashkovich, Kanstantsin, et al.
Pubblicazione: (2026)

Covering and packing mixed-integer linear programs with a fixed number of constraints: Approximation and convex hull
di: Grobben, Kobe, et al.
Pubblicazione: (2025)

Submodular Maximization over a Matroid $k$-Intersection: Multiplicative Improvement over Greedy
di: Feldman, Moran, et al.
Pubblicazione: (2026)

Random-Order Online Independent Set of Intervals and Hyperrectangles
di: Garg, Mohit, et al.
Pubblicazione: (2024)

Shortest Paths without a Map, but with an Entropic Regularizer
di: Bubeck, Sébastien, et al.
Pubblicazione: (2022)

Nearly Tight Sample Complexity for Matroid Online Contention Resolution
di: Feldman, Moran, et al.
Pubblicazione: (2025)

Extensions of the regret-minimization algorithm for optimal design
di: Chen, Youguang, et al.
Pubblicazione: (2025)

Online Trading as a Secretary Problem Variant
di: Chen, Xujin, et al.
Pubblicazione: (2026)

Prediction-Augmented Mechanism Design for Weighted Facility Location
di: Shi, Yangguang, et al.
Pubblicazione: (2025)

Choosing Behind the Veil: Tight Bounds for Identity-Blind Online Algorithms
di: Ezra, Tomer, et al.
Pubblicazione: (2024)

Advancing Stochastic 3-SAT Solvers by Dissipating Oversatisfied Constraints
di: Schwardt, J., et al.
Pubblicazione: (2025)

Incremental-Decremental Maximization
di: Disser, Yann, et al.
Pubblicazione: (2025)

A note on the parameter $\ell$ in Buchbinder--Feldman's deterministic submodular matroid algorithm
di: Li, Shisheng
Pubblicazione: (2026)

Deterministically Simulating Barely Random Algorithms in the Random-Order Arrival Model
di: Borodin, Allan, et al.
Pubblicazione: (2025)

Pandora's Problem with Combinatorial Cost
di: Berger, Ben, et al.
Pubblicazione: (2023)

Single-Sample Prophet Inequalities via Greedy-Ordered Selection
di: Caramanis, Constantine, et al.
Pubblicazione: (2021)

A Fast Monte Carlo algorithm for evaluating matrix functions with application in complex networks
di: Guidotti, Nicolas L., et al.
Pubblicazione: (2023)

Correcting the Foundational Analysis of Karp--Vazirani--Vazirani (STOC 1990): A Rigorous Revision of the $1-1/e$ Upper Bound
di: Xu, Pan
Pubblicazione: (2025)

Improved Regret Guarantees for Online Mirror Descent using a Portfolio of Mirror Maps
di: Gupta, Swati, et al.
Pubblicazione: (2026)

Adaptive Approximation Schemes for Matching Queues
di: AmaniHamedani, Alireza, et al.
Pubblicazione: (2025)

Prophet Upper Bounds for Online Matching and Auctions
di: Soto, José, et al.
Pubblicazione: (2024)

Can Synthetic Data Improve Symbolic Regression Extrapolation Performance?
di: Ramlan, Fitria Wulandari, et al.
Pubblicazione: (2025)

Improved Approximations for Stationary Bipartite Matching: Beyond Probabilistic Independence
di: AmaniHamedani, Alireza, et al.
Pubblicazione: (2024)

Extending Exact Integrality Gap Computations for the Metric TSP
di: Cook, William, et al.
Pubblicazione: (2026)

On the PLS-Completeness of $k$-Opt Local Search for the Traveling Salesman Problem
di: Heimann, Sophia, et al.
Pubblicazione: (2026)

The Power of Filling in Balanced Allocations
di: Los, Dimitrios, et al.
Pubblicazione: (2022)

Mean-Biased Processes for Balanced Allocations
di: Los, Dimitrios, et al.
Pubblicazione: (2023)