Minimizing ratio of monotone non-submodular functions

DOI10.1007/s40305-019-00244-1zbMath1438.90291OpenAlexW2923536170WikidataQ128201307 ScholiaQ128201307MaRDI QIDQ2326079

Dongmei Zhang, Yanjun Jiang, Yi-Jing Wang, Da-Chuan Xu

Publication date: 4 October 2019

Published in: Journal of the Operations Research Society of China (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s40305-019-00244-1

zbMATH Keywords

greedy algorithmset functionsnon-submodularminimizing ratio

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items

A constrained two-stage submodular maximization ⋮ Sequence submodular maximization meets streaming

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on submodular function minimization with covering type linear constraints
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• The submodular knapsack polytope
• The ellipsoid method and its consequences in combinatorial optimization
• An analysis of the greedy algorithm for the submodular set covering problem
• Cores of convex games
• The Quickest Transshipment Problem
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• An analysis of approximations for maximizing submodular set functions—I
• Polymatroidal dependence structure of a set of random variables
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Submodular Maximization with Cardinality Constraints

This page was built for publication: Minimizing ratio of monotone non-submodular functions