Maximizing a submodular function with viability constraints

DOI10.1007/978-3-642-40450-4_35zbMATH Open1357.92061arXiv1611.05753OpenAlexW2173482757MaRDI QIDQ513299FDOQ513299

Authors: Wolfgang Dvořák, David P. Williamson, Monika R. Henzinger 

Publication date: 6 March 2017

Published in: Algorithmica, Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: We study the problem of maximizing a monotone submodular function with viability constraints. This problem originates from computational biology, where we are given a phylogenetic tree over a set of species and a directed graph, the so-called food web, encoding viability constraints between these species. These food webs usually have constant {depth}. The goal is to select a subset of $k$ species that satisfies the viability constraints and has maximal phylogenetic diversity. As this problem is known to be NP-hard, we investigate approximation algorithms. We present the first constant factor approximation algorithm if the depth is constant. Its approximation ratio is $(1-frac1sqrte)$. This algorithm not only applies to phylogenetic trees with viability constraints but for arbitrary monotone submodular set functions with viability constraints. Second, we show that there is no $(1-1/e+epsilon)$-approximation algorithm for our problem setting (even for additive functions) and that there is no approximation algorithm for a slight extension of this setting.

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

Recommendations

• Maximizing a submodular function with viability constraints
• Maximizing a class of submodular utility functions with constraints
• Maximization of constrained non-submodular functions
• Maximizing a class of submodular utility functions
• Maximizing Non-monotone Submodular Functions
• Maximizing a non-decreasing non-submodular function subject to various types of constraints
• Maximizing submodular set functions subject to multiple linear constraints
• Maximizing a monotone submodular function subject to a matroid constraint
• Maximization of \(k\)-submodular function with a matroid constraint
• Maximizing \(k\)-submodular functions and beyond

zbMATH Keywords

approximation algorithmsphylogenetic diversitysubmodular functionsviability constraints

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Problems related to evolution (92D15) Population dynamics (general) (92D25) Ecology (92D40) Approximation algorithms (68W25)

Cites Work

• A threshold of ln n for approximating set cover
• Title not available (Why is that?)
• The hardness of approximation: Gap location
• The budgeted maximum coverage problem
• An analysis of approximations for maximizing submodular set functions—I
• Non-monotone submodular maximization under matroid and knapsack constraints
• The Noah's Ark Problem
• Symmetry and Approximability of Submodular Maximization Problems
• Two variations of the minimum Steiner problem
• Optimizing phylogenetic diversity under constraints
• Maximizing a submodular function with viability constraints
• Optimizing phylogenetic diversity with ecological constraints
• Budgeted nature reserve selection with diversity feature loss and arbitrary split systems

Cited In (4)

• Submodular Maximization With Limited Function Access
• Maximizing a submodular function with viability constraints
• Maximizing a class of submodular utility functions with constraints
• Optimizing phylogenetic diversity with ecological constraints

This page was built for publication: Maximizing a submodular function with viability constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q513299)