Copertina

Adaptivity Gaps for Stochastic Probing with Subadditive Functions

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Li, Jian, Liu, Yinchen, Zhang, Yiran
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Sequential Testing with Subadditive Costs
di: Harris, Blake, et al.
Pubblicazione: (2025)

Universal Optimization for Non-Clairvoyant Subadditive Joint Replenishment
di: Ezra, Tomer, et al.
Pubblicazione: (2024)

Stochastic Knapsack: Semi-Adaptivity Gaps and Improved Approximation
di: Barak, Zohar, et al.
Pubblicazione: (2026)

Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
di: Jiang, Cheng, et al.
Pubblicazione: (2026)

New Results on a General Class of Minimum Norm Optimization Problems
di: Chen, Kuowen, et al.
Pubblicazione: (2025)

Non-Adaptive Evaluation of $k$-of-$n$ Functions: Tight Gap and a Unit-Cost PTAS
di: Nielsen, Mads Anker, et al.
Pubblicazione: (2025)

Approximating Asymmetric A Priori TSP beyond the Adaptivity Gap
di: Christalla, Manuel, et al.
Pubblicazione: (2025)

Optimal Non-Adaptive Cell Probe Dictionaries and Hashing
di: Larsen, Kasper Green, et al.
Pubblicazione: (2023)

A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed Graphs
di: Chen, Kuowen, et al.
Pubblicazione: (2025)

Optimality of Non-Adaptive Algorithms in Online Submodular Welfare Maximization with Stochastic Outcomes
di: Udwani, Rajan
Pubblicazione: (2024)

Commitment Gap via Correlation Gap
di: Chawla, Shuchi, et al.
Pubblicazione: (2025)

Adaptive Hashing: Faster Hash Functions with Fewer Collisions
di: Melis, Gábor
Pubblicazione: (2026)

On the Advantage of Adaptivity for Sampling with Cell Probes
di: Byramji, Farzan, et al.
Pubblicazione: (2026)

DNA Probe Computing System for Solving NP-Complete Problems
di: Xu, Jin, et al.
Pubblicazione: (2025)

Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems
di: Dughmi, Shaddin, et al.
Pubblicazione: (2025)

Gapped String Indexing in Subquadratic Space and Sublinear Query Time
di: Bille, Philip, et al.
Pubblicazione: (2022)

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

Tight Gap-Dependent Memory-Regret Trade-Off for Single-Pass Streaming Stochastic Multi-Armed Bandits
di: Ye, Zichun, et al.
Pubblicazione: (2025)

Adaptive Multi-Round Allocation with Stochastic Arrivals
di: Pan, Yuqi, et al.
Pubblicazione: (2026)

Two-sided Assortment Optimization: Adaptivity Gaps and Approximation Algorithms
di: Housni, Omar El, et al.
Pubblicazione: (2024)

Stochastic Embedding of Digraphs into DAGs
di: Filtser, Arnold
Pubblicazione: (2025)

Layered Graph Drawing with Few Gaps and Few Crossings
di: Dobler, Alexander, et al.
Pubblicazione: (2025)

Closing the Gap Between Directed Hopsets and Shortcut Sets
di: Bernstein, Aaron, et al.
Pubblicazione: (2022)

On Differential Privacy for Adaptively Solving Search Problems via Sketching
di: Feng, Shiyuan, et al.
Pubblicazione: (2025)

Tight Analyses of Ordered and Unordered Linear Probing
di: Braverman, Mark, et al.
Pubblicazione: (2025)

Scheduling on a Stochastic Number of Machines
di: Buchem, Moritz, et al.
Pubblicazione: (2024)

Subsequences With Generalised Gap Constraints: Upper and Lower Complexity Bounds
di: Manea, Florin, et al.
Pubblicazione: (2024)

Identifying Approximate Minimizers under Stochastic Uncertainty
di: Al-Thani, Hessa, et al.
Pubblicazione: (2025)

Nearly Optimal Bounds for Stochastic Online Sorting
di: Hu, Yang
Pubblicazione: (2025)

Limitations of Stochastic Selection with Pairwise Independent Priors
di: Dughmi, Shaddin, et al.
Pubblicazione: (2023)

First Order Stochastic Optimization with Oblivious Noise
di: Diakonikolas, Ilias, et al.
Pubblicazione: (2024)

Efficient Deterministic Algorithms for Maximizing Symmetric Submodular Functions
di: Wan, Zongqi, et al.
Pubblicazione: (2024)

A Linear Time Gap-ETH-Tight Approximation Scheme for Euclidean TSP
di: Mömke, Tobias, et al.
Pubblicazione: (2024)

Stochastic Minimum Spanning Trees with a Single Sample
di: Hoeksma, Ruben, et al.
Pubblicazione: (2024)

Online Multi-level Aggregation with Delays and Stochastic Arrivals
di: Mari, Mathieu, et al.
Pubblicazione: (2024)

Near-optimal Algorithms for Stochastic Online Bin Packing
di: Ayyadevara, Nikhil, et al.
Pubblicazione: (2022)

Stochastic Traveling Salesperson Problem with Neighborhoods for Object Detection
di: Peng, Cheng, et al.
Pubblicazione: (2024)

Stochastic Optimization and Learning for Two-Stage Supplier Problems
di: Brubach, Brian, et al.
Pubblicazione: (2020)

Mind the Gap. Doubling Constant Parametrization of Weighted Problems: TSP, Max-Cut, and More
di: Stoian, Mihail
Pubblicazione: (2026)

A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP
di: Kalavas, Andreas, et al.
Pubblicazione: (2025)