Cover Image

Efficient Approximation Schemes for Stochastic Probing and Selection-Stopping Problems

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Segev, Danny, Singla, Sahil
Format:	Preprint
Published:	2020
Subjects:	Data Structures and Algorithms Computer Science and Game Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Secretary, Prophet, and Stochastic Probing via Big-Decisions-First
by: Rubinstein, Aviad, et al.
Published: (2026)

Sample Complexity of Posted Pricing for a Single Item
by: Jin, Billy, et al.
Published: (2024)

Bandit Sequential Posted Pricing via Half-Concavity
by: Singla, Sahil, et al.
Published: (2023)

Single-Sample and Robust Online Resource Allocation
by: Ghuge, Rohan, et al.
Published: (2025)

Revenue Maximization in Choice-Based Matching Markets
by: Nissim, Dan, et al.
Published: (2024)

Stochastic Online Correlated Selection
by: Chen, Ziyun, et al.
Published: (2024)

Optimal Stopping with Interdependent Values
by: Mauras, Simon, et al.
Published: (2024)

Polynomial-Time Approximation Schemes via Utility Alignment: Unit-Demand Pricing and More
by: Bowers, Robin, et al.
Published: (2025)

Improved Mechanisms and Prophet Inequalities for Graphical Dependencies
by: Livanos, Vasilis, et al.
Published: (2024)

Online Combinatorial Allocations and Auctions with Few Samples
by: Dütting, Paul, et al.
Published: (2024)

Static Pricing for Online Selection Problem and its Variants
by: Sun, Bo, et al.
Published: (2024)

Beyond the Half-Approximation: Fair and Efficient Online Class Matching
by: Borst, Sander, et al.
Published: (2026)

Logarithmic Approximation for Road Pricing on Grids
by: Constantinescu, Andrei, et al.
Published: (2025)

Welfare Approximation in Additively Separable Hedonic Games
by: Bullinger, Martin, et al.
Published: (2025)

Fair Repetitive Interval Scheduling
by: Heeger, Klaus, et al.
Published: (2024)

An FPTAS for 7/9-Approximation to Maximin Share Allocations
by: Huang, Xin, et al.
Published: (2025)

Approximating Nash Social Welfare by Matching and Local Search
by: Garg, Jugal, et al.
Published: (2022)

More Efforts Towards Fixed-Parameter Approximability of Multiwinner Rules
by: Gupta, Sushmita, et al.
Published: (2025)

Constant Approximation for Weighted Nash Social Welfare with Submodular Valuations
by: Feng, Yuda, et al.
Published: (2024)

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

The Average-Value Allocation Problem
by: Bhawalkar, Kshipra, et al.
Published: (2024)

A Note on Approximating Weighted Nash Social Welfare with Additive Valuations
by: Feng, Yuda, et al.
Published: (2024)

Nash Social Welfare with Submodular Valuations: Approximation Algorithms and Integrality Gaps
by: Bei, Xiaohui, et al.
Published: (2025)

The Secretary Problem with Predicted Additive Gap
by: Braun, Alexander, et al.
Published: (2024)

Canadian Traveller Problems in Temporal Graphs
by: Bellitto, Thomas, et al.
Published: (2024)

Computing Approximately Proportional Allocations of Indivisible Goods: Beyond Additive and Monotone Valuations
by: Andersen, Martin Jupakkal, et al.
Published: (2025)

Edge-weighted Online Stochastic Matching Under Jaillet-Lu LP
by: Yan, Shuyi
Published: (2025)

Approximation Algorithms for the Weighted Nash Social Welfare via Convex and Non-Convex Programs
by: Brown, Adam, et al.
Published: (2024)

The Min Max Average Cycle Weight Problem
by: Elmalem, Noga Klein, et al.
Published: (2025)

Edge-weighted Online Stochastic Matching: Beating $1-\frac1e$
by: Yan, Shuyi
Published: (2022)

Structural and Algorithmic Results for Stable Cycles and Partitions in the Roommates Problem
by: Glitzner, Frederik, et al.
Published: (2024)

Beyond matroids: Secretary Problem and Prophet Inequality with general constraints
by: Rubinstein, Aviad
Published: (2016)

Risk-Sensitive Online Selection with Bounded Adaptivity
by: Nekouyan, Hossein, et al.
Published: (2025)

Solving Woeginger's Hiking Problem: Wonderful Partitions in Anonymous Hedonic Games
by: Constantinescu, Andrei, et al.
Published: (2023)

Addressing Bias in Online Selection with Limited Budget of Comparisons
by: Benomar, Ziyad, et al.
Published: (2023)

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

Threshold Policies with Tight Guarantees for Online Selection with Convex Costs
by: Tan, Xiaoqi, et al.
Published: (2023)

Setting Targets is All You Need:Improved Order Competitive Ratio for Online Selection
by: Chen, Liyan, et al.
Published: (2024)

Efficient Two-Sided Markets with Limited Information
by: Dütting, Paul, et al.
Published: (2020)

Revisiting Fair and Efficient Allocations for Bivalued Goods
by: Liu, Hui, et al.
Published: (2026)