Multiple knapsack-constrained monotone DR-submodular maximization on distributive lattice -- continuous greedy algorithm on median complex --
From MaRDI portal
Publication:2149546
DOI10.1007/s10107-021-01620-7zbMath1494.90098arXiv1907.04279OpenAlexW3128475368MaRDI QIDQ2149546
Takanori Maehara, So Nakashima, Yutaro Yamaguchi
Publication date: 29 June 2022
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1907.04279
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Braids, posets and orthoschemes
- Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
- Matroids on partially ordered sets
- A note on maximizing a submodular set function subject to a knapsack constraint
- Maximizing monotone submodular functions over the integer lattice
- Pipage rounding: a new method of constructing algorithms with proven performance guarantee
- Graphs of some CAT(0) complexes
- Rank axiom of modular supermatroids: a connection with directional DR submodular functions
- Submodular Function Maximization on the Bounded Integer Lattice
- Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
- A NOTE ON SUBMODULAR FUNCTIONS ON DISTRIBUTIVE LATTICES
- Weakly Modular Graphs and Nonpositive Curvature
- Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
- An analysis of approximations for maximizing submodular set functions—I
- Minimizing a Submodular Function on a Lattice
- L-CONVEXITY ON GRAPH STRUCTURES
- Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
- Probability Inequalities Related to Markov's Theorem
- Probability Inequalities for Sums of Bounded Random Variables