Approximation algorithms for stochastic combinatorial optimization problems
From MaRDI portal
Publication:290321
DOI10.1007/s40305-015-0116-9zbMath1385.68052OpenAlexW2281909915MaRDI QIDQ290321
Publication date: 1 June 2016
Published in: Journal of the Operations Research Society of China (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s40305-015-0116-9
Stochastic programming (90C15) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items (4)
Approximation algorithm for the stochastic prize-collecting set multicover problem ⋮ Min max min robust (relative) regret combinatorial optimization ⋮ Approximation algorithm for stochastic set cover problem ⋮ Approximation algorithms for stochastic set cover and single sink rent-or-buy with submodular penalty
Cites Work
- A Single-Sample Multiple Decision Procedure for Ranking Means of Normal Populations with known Variances
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Four proofs of Gittins' multiarmed bandit theorem
- Thresholded covering algorithms for robust and max-min optimization
- When LP is the cure for your matching woes: improved bounds for stochastic matchings
- A PTAS for the chance-constrained knapsack problem with random item sizes
- A fully polynomial-time approximation scheme for approximating a sum of random variables
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Two-stage robust network design with exponential scenarios
- Improved analysis of the greedy algorithm for stochastic matching
- Hedging uncertainty: approximation algorithms for stochastic optimization problems
- An approximation theorem for the Poisson binomial distribution
- Linear Programming under Uncertainty
- How the Experts Algorithm Can Help Solve LPs Online
- Matroid Secretary Problem in the Random-Assignment Model
- Multi-parameter mechanism design and sequential posted pricing
- An improved LP-based approximation for steiner tree
- Online Stochastic Matching: Online Actions Based on Offline Statistics
- A Dynamic Near-Optimal Algorithm for Online Linear Programming
- Greedy Algorithms for Steiner Forest
- Approximation algorithms for restless bandit problems
- Introduction to Stochastic Programming
- The Design of Approximation Algorithms
- Optimal paths in graphs with stochastic or multidimensional weights
- Approximating extent measures of points
- Sampling and Cost-Sharing: Approximation Algorithms for Stochastic Optimization Problems
- Sampling-Based Approximation Algorithms for Multistage Stochastic Optimization
- Kidney Exchange
- Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
- A Plant Location Guide for the Unsure: Approximation Algorithms for Min-Max Location Problems
- Improved Approximation Algorithms for Stochastic Matching
- An approximation scheme for stochastic linear programming and its application to stochastic integer programs
- Dependent rounding and its applications to approximation algorithms
- AdWords and generalized online matching
- Boosted sampling
- Universal approximations for TSP, Steiner tree, and set cover
- Improved lower and upper bounds for universal TSP in planar metrics
- Improved Bounds for Online Stochastic Matching
- Online Stochastic Packing Applied to Display Ad Allocation
- Approximation Algorithms for Reliable Stochastic Combinatorial Optimization
- Stochastic Steiner Tree with Non-uniform Inflation
- Approximating Matches Made in Heaven
- On Optimal Replacement Policies
- Complexity of some parametric integer and network programming problems
- The Complexity of Markov Decision Processes
- Renewal Decision Problem-Random Horizon
- Renewal Decisions when Category Life Distributions are of Phase-Type
- A Renewal Decision Problem
- Allocating Bandwidth for Bursty Connections
- Online Contention Resolution Schemes
- Smallest enclosing ball for probabilistic data
- Real Analysis and Probability
- Conservation Laws, Extended Polymatroids and Multiarmed Bandit Problems; A Polyhedral Approach to Indexable Systems
- A Stochastic Probing Problem with Applications
- Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
- Online Stochastic Matching: Beating 1-1/e
- A constant-factor approximation for stochastic Steiner forest
- Matroid Secretary for Regular and Decomposable Matroids
- Arc Reduction and Path Preference in Stochastic Acyclic Networks
- Online Stochastic Matching: New Algorithms with Better Bounds
- Primal beats dual on online packing LPs in the random-order model
- Multi-armed Bandits with Metric Switching Costs
- Improved Bounds in Stochastic Matching and Optimization
- Online Stochastic Matching with Unequal Probabilities
- Fast Algorithms for Online Stochastic Convex Programming
- A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem
- A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage
- Improvements and Generalizations of Stochastic Knapsack and Multi-Armed Bandit Approximation Algorithms: Extended Abstract
- Approximation Algorithms for 2-Stage Stochastic Optimization Problems
- Strict Cost Sharing Schemes for Steiner Forest
- Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
- Matroid prophet inequalities
- On the Adaptivity Gap of Stochastic Orienteering
- A Utility Equivalence Theorem for Concave Functions
- Online bipartite matching with unknown distributions
- Online bipartite matching with random arrivals
- Robust Combinatorial Optimization with Exponential Scenarios
- Stochastic Shortest Paths Via Quasi-convex Maximization
- Pay Today for a Rainy Day: Improved Approximation Algorithms for Demand-Robust Min-Cut and Shortest Path Problems
- Prediction, Learning, and Games
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers
- Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems
- Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits
- Simplex partitioning via exponential clocks and the multiway cut problem
This page was built for publication: Approximation algorithms for stochastic combinatorial optimization problems
