Online Submodular Maximization Problem with Vector Packing Constraint.

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

zbMATH Keywords

vector packingsubmodular maximizationfree-disposal

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Online algorithms; streaming algorithms (68W27)

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.