Online Submodular Maximization Problem with Vector Packing Constraint.
From MaRDI portal
Publication:5111710
DOI10.4230/LIPIcs.ESA.2017.24zbMath1442.68272arXiv1706.06922MaRDI QIDQ5111710
Zhihao Gavin Tang, T.-H. Hubert Chan, Shaofeng H.-C. Jiang, Xiaowei Wu
Publication date: 27 May 2020
Full work available at URL: https://arxiv.org/abs/1706.06922
Related Items
Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model, Online Submodular Maximization Problem with Vector Packing Constraint., Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint, Multi-pass streaming algorithms for monotone submodular function maximization
Cites Work
- Unnamed Item
- Unnamed Item
- Online scheduling with preemption or non-completion penalties
- Randomized algorithms for online knapsack problems
- Online unweighted knapsack problem with removal cost
- Resource constrained scheduling as generalized bin packing
- On the complexity of approximating \(k\)-set packing
- Geometry of Online Packing Linear Programs
- Online Bipartite Matching with Decomposable Weights
- Improved Bounds for Online Preemptive Matching
- Inapproximability of b-Matching in k-Uniform Hypergraphs
- Online Primal-Dual Algorithms for Covering and Packing
- On k-Column Sparse Packing Programs
- Online Stochastic Packing Applied to Display Ad Allocation
- Optimal Resource Augmentations for Online Knapsack
- Packing Small Vectors
- Online Submodular Maximization with Free Disposal: Randomization Beats ¼ for Partition Matroids
- Beating ratio 0.5 for weighted oblivious matching problems
- Near Optimal Online Algorithms and Fast Approximation Algorithms for Resource Allocation Problems
- Online Submodular Maximization Problem with Vector Packing Constraint.
- Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
- Primal beats dual on online packing LPs in the random-order model
- Online Submodular Maximization with Preemption
- Tight bounds for online vector bin packing
- Randomized Primal-Dual Analysis of RANKING for Online Bipartite Matching