Maximizing monotone submodular functions over the integer lattice

DOI10.1007/s10107-018-1324-yzbMath1406.90108arXiv1503.01218OpenAlexW2889329271MaRDI QIDQ1801020

Yuichi Yoshida, Tasuku Soma

Publication date: 26 October 2018

Published in: Mathematical Programming. Series A. Series B, Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1503.01218

zbMATH Keywords

integer latticesubmodular functionsDR-submodular functions

Mathematics Subject Classification ID

Integer programming (90C10) Nonlinear programming (90C30) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (26)

Multiple knapsack-constrained monotone DR-submodular maximization on distributive lattice -- continuous greedy algorithm on median complex -- ⋮ Maximization of monotone non-submodular functions with a knapsack constraint over the integer lattice ⋮ Streaming algorithms for maximizing DR-submodular functions with \(d\)-knapsack constraints ⋮ Maximizing a monotone non-submodular function under a knapsack constraint ⋮ An optimal streaming algorithm for non-submodular functions maximization on the integer lattice ⋮ A fast and deterministic algorithm for knapsack-constrained monotone DR-submodular maximization over an integer lattice ⋮ A generalized-polymatroid approach to disjoint common independent sets in two matroids ⋮ Multi-objective evolutionary algorithms are generally good: maximizing monotone submodular functions over sequences ⋮ Streaming submodular maximization under \(d\)-knapsack constraints ⋮ On streaming algorithms for maximizing a supermodular function plus a MDR-submodular function on the integer lattice ⋮ A single factor approximation ratio algorithm for DR-submodular maximization on integer lattice beyond non-negativity and monotonicity ⋮ Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity ⋮ A note for approximating the submodular cover problem over integer lattice with low adaptive and query complexities ⋮ A binary search double greedy algorithm for non-monotone DR-submodular maximization ⋮ Approximation algorithm of maximizing non-monotone non-submodular functions under knapsack constraint ⋮ Community-based rumor blocking maximization in social networks: algorithms and analysis ⋮ Profit maximization in social networks and non-monotone DR-submodular maximization ⋮ Parametric monotone function maximization with matroid constraints ⋮ Community-based rumor blocking maximization in social networks ⋮ Monotone submodular maximization over the bounded integer lattice with cardinality constraints ⋮ Maximizing monotone submodular functions over the integer lattice ⋮ Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint ⋮ A fast double greedy algorithm for non-monotone DR-submodular function maximization ⋮ Rank axiom of modular supermatroids: a connection with directional DR submodular functions ⋮ Streaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer lattice ⋮ Streaming Algorithms for Maximizing Monotone DR-Submodular Functions with a Cardinality Constraint on the Integer Lattice

Cites Work

• Unnamed Item
• Unnamed Item
• Submodular function minimization
• Testing membership in matroid polyhedra
• A note on maximizing a submodular set function subject to a knapsack constraint
• Maximizing monotone submodular functions over the integer lattice
• Submodular functions and optimization.
• Submodular Function Maximization on the Bounded Integer Lattice
• Maximizing Non-monotone Submodular Functions
• A threshold of ln n for approximating set cover
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS
• Discrete Convex Analysis
• Deterministic Algorithms for Submodular Maximization Problems
• Improved Approximation Algorithms for k-Submodular Function Maximization
• Submodular Maximization with Cardinality Constraints
• Maximizing Bisubmodular and k-Submodular Functions
• Fast algorithms for maximizing submodular functions
• Online submodular welfare maximization: Greedy is optimal

This page was built for publication: Maximizing monotone submodular functions over the integer lattice