Near-optimal sparsifiers for stochastic knapsack and assignment problems
From MaRDI portal
Cites work
- A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
- Approximation algorithms for allocation problems: improving the factor of 1 - 1/e
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- On sparsification of stochastic packing problems
- On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP
- On the complexity of k-SAT
- Query efficient weighted stochastic matching
- Reducibility among combinatorial problems
- Stochastic matching with few queries: (1-ε) approximation
- Stochastic Matching with Few Queries: New Algorithms and Tools
- Stochastic minimum vertex cover in general graphs: a 3/2-approximation
- Stochastic packing integer programs with few queries
- Stochastic vertex cover with few queries
- Stochastic weighted matching: (1- ) approximation
- The design of approximation algorithms
- Towards a unified theory of sparsification for matching problems
This page was built for publication: Near-optimal sparsifiers for stochastic knapsack and assignment problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7445573)