A note on submodular function minimization with covering type linear constraints

DOI10.1007/S00453-017-0363-8zbMath1402.90150OpenAlexW2748419052MaRDI QIDQ722536

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

zbMATH Keywords

primal-dual approximation algorithmsubmodular function minimization

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (4)

Approximation algorithms for the submodular edge cover problem with submodular penalties ⋮ A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem ⋮ Finding Submodularity Hidden in Symmetric Difference ⋮ Minimizing ratio of monotone non-submodular functions

Cites Work

• Unnamed Item
• Graph cuts with interacting edge weights: examples, approximations, and algorithms
• Primal-dual schema for capacitated covering problems
• The ellipsoid method and its consequences in combinatorial optimization
• Geometric algorithms and combinatorial optimization
• Minimizing symmetric submodular functions
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost
• Submodular Function Minimization under a Submodular Set Covering Constraint
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• Submodular Approximation: Sampling-based Algorithms and Lower Bounds
• Discrete Convex Analysis
• Submodular Function Minimization under Covering Constraints
• Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions
• A 2-APPROXIMATION ALGORITHM FOR THE MINIMUM KNAPSACK PROBLEM WITH A FORCING GRAPH
• Learning with Submodular Functions: A Convex Optimization Perspective

This page was built for publication: A note on submodular function minimization with covering type linear constraints