A note on submodular function minimization with covering type linear constraints
From MaRDI portal
Publication:722536
DOI10.1007/S00453-017-0363-8zbMATH Open1402.90150OpenAlexW2748419052MaRDI QIDQ722536FDOQ722536
Authors: Naoyuki Kamiyama 
Publication date: 26 July 2018
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-017-0363-8
Recommendations
- Submodular function minimization under a submodular set covering constraint
- Submodular function minimization with submodular set covering constraints and precedence constraints
- Complexity and approximations for submodular minimization problems on two variables per inequality constraints
- Maximizing submodular set functions subject to multiple linear constraints
- Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost
Cites Work
- Discrete Convex Analysis
- Geometric algorithms and combinatorial optimization
- The ellipsoid method and its consequences in combinatorial optimization
- Title not available (Why is that?)
- Minimizing symmetric submodular functions
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- Submodular Function Minimization under Covering Constraints
- Graph cuts with interacting edge weights: examples, approximations, and algorithms
- Submodular Approximation: Sampling-based Algorithms and Lower Bounds
- Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions
- Submodular function minimization under a submodular set covering constraint
- Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost
- A 2-APPROXIMATION ALGORITHM FOR THE MINIMUM KNAPSACK PROBLEM WITH A FORCING GRAPH
- Learning with submodular functions: a convex optimization perspective
- Primal-dual schema for capacitated covering problems
Cited In (9)
- Minimizing ratio of monotone non-submodular functions
- A note on submodular function minimization by Chubanov's LP algorithm
- Approximation algorithms for the submodular hitting set problem
- Finding submodularity hidden in symmetric difference
- Submodular function minimization with submodular set covering constraints and precedence constraints
- Submodular function minimization under a submodular set covering constraint
- Approximation algorithms for the submodular edge cover problem with submodular penalties
- Complexity and approximations for submodular minimization problems on two variables per inequality constraints
- A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem
This page was built for publication: A note on submodular function minimization with covering type linear constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q722536)
