Parametric monotone function maximization with matroid constraints
From MaRDI portal
Publication:2010096
DOI10.1007/s10898-019-00800-2zbMath1432.90133OpenAlexW2955556456MaRDI QIDQ2010096
Qizhi Fang, Suning Gong, Wenjing Liu, Qingqin Nong
Publication date: 3 December 2019
Published in: Journal of Global Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10898-019-00800-2
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Related Items (21)
On maximizing the difference between an approximately submodular function and a linear function subject to a matroid constraint ⋮ A linear-time streaming algorithm for cardinality-constrained maximizing monotone non-submodular set functions ⋮ Maximization of monotone non-submodular functions with a knapsack constraint over the integer lattice ⋮ Maximizing a non-decreasing non-submodular function subject to various types of constraints ⋮ Bicriteria algorithms to balance coverage and cost in team formation under online model ⋮ Online bicriteria algorithms to balance coverage and cost in team formation ⋮ Parallelized maximization of nonsubmodular function subject to a cardinality constraint ⋮ Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint ⋮ Fast algorithms for maximizing monotone nonsubmodular functions ⋮ Fast algorithms for maximizing monotone nonsubmodular functions ⋮ Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint ⋮ Improved algorithms for non-submodular function maximization problem ⋮ Parallelized maximization of nonsubmodular function subject to a cardinality constraint ⋮ Maximization problems of balancing submodular relevance and supermodular diversity ⋮ Bicriteria streaming algorithms to balance gain and cost with cardinality constraint ⋮ Streaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer lattice ⋮ The submodularity of two-stage stochastic maximum-weight independent set problems ⋮ An adaptive algorithm for maximization of non-submodular function with a matroid constraint ⋮ Two approximation algorithms for maximizing nonnegative weakly monotonic set functions ⋮ Non-Submodular Maximization with Matroid and Knapsack Constraints ⋮ Randomized Parallel Algorithm for Maximizing Nonsubmodular Function Subject to Cardinality Constraint
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A framework of discrete DC programming by discrete convex analysis
- Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
- Correlation inequalities on some partially ordered sets
- Solving the degree-concentrated fault-tolerant spanning subgraph problem by DC programming
- Maximizing monotone submodular functions over the integer lattice
- An analysis of the greedy algorithm for the submodular set covering problem
- Pipage rounding: a new method of constructing algorithms with proven performance guarantee
- Set function optimization
- Combinatorial auctions with decreasing marginal utilities
- Submodular functions and optimization.
- Constrained Monotone Function Maximization and the Supermodular Degree
- Welfare maximization and the supermodular degree
- An analysis of approximations for maximizing submodular set functions—I
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
- Matroids and the greedy algorithm
This page was built for publication: Parametric monotone function maximization with matroid constraints
