Online Submodular Maximization Problem with Vector Packing Constraint.
From MaRDI portal
Publication:5111710
DOI10.4230/LIPIcs.ESA.2017.24zbMath1442.68272arXiv1706.06922OpenAlexW2963788302MaRDI 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 (4)
Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint ⋮ Multi-pass streaming algorithms for monotone submodular function maximization ⋮ Online Submodular Maximization Problem with Vector Packing Constraint. ⋮ Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
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
This page was built for publication: Online Submodular Maximization Problem with Vector Packing Constraint.
