Stochastic packing integer programs with few queries
From MaRDI portal
Abstract: We consider a stochastic variant of the packing-type integer linear programming problem, which contains random variables in the objective vector. We are allowed to reveal each entry of the objective vector by conducting a query, and the task is to find a good solution by conducting a small number of queries. We propose a general framework of adaptive and non-adaptive algorithms for this problem, and provide a unified methodology for analyzing the performance of those algorithms. We also demonstrate our framework by applying it to a variety of stochastic combinatorial optimization problems such as matching, matroid, and stable set problems.
Recommendations
Cites work
- A stochastic probing problem with applications
- Adaptivity and approximation for stochastic packing problems
- Adaptivity gaps for stochastic probing: submodular and XOS functions
- An algorithm for weighted fractional matroid matching
- Approximating Matches Made in Heaven
- Approximating the stochastic Knapsack problem: the benefit of adaptivity
- Approximation algorithms for covering/packing integer programs
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Degree bounded matroids and submodular flows
- Generalized hypergraph matching via iterated packing and local ratio
- scientific article; zbMATH DE number 3637616 (Why is no real title available?)
- scientific article; zbMATH DE number 6297805 (Why is no real title available?)
- scientific article; zbMATH DE number 3422402 (Why is no real title available?)
- Improved analysis of the greedy algorithm for stochastic matching
- Iterative packing for demand and hypergraph matching
- Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
- Kidney Exchange
- Matroid matching: the power of local search
- On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
- On the theory of graphs
- Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- Stochastic matching with commitment
- Submodular stochastic probing on matroids
- The Demand-Matching Problem
- When LP is the cure for your matching woes: improved bounds for stochastic matchings
Cited in
(10)- Query-competitive sorting with uncertainty
- Round-competitive algorithms for uncertainty problems with parallel queries
- Adaptivity and approximation for stochastic packing problems
- Stochastic packing integer programs with few queries
- Query minimization under stochastic uncertainty
- Set selection under explorable stochastic uncertainty via covering techniques
- Learning-augmented query policies for minimum spanning tree with uncertainty
- Approximation algorithms for k-scenario matching
- Round-competitive algorithms for uncertainty problems with parallel queries
- On the complexity of knapsack under explorable uncertainty: hardness and algorithms
This page was built for publication: Stochastic packing integer programs with few queries
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2191766)
