Fast algorithms for maximizing monotone nonsubmodular functions

DOI10.1007/978-3-030-57602-8_19zbMath1485.90114OpenAlexW3048198878MaRDI QIDQ5918332

Miaomiao Hu, Bin Liu

Publication date: 5 July 2021

Published in: Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-57602-8_19

zbMATH Keywords

approximation algorithmmatroid constraintmaximizationcardinality constraintnonsubmodular function

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (1)

A linear-time streaming algorithm for cardinality-constrained maximizing monotone non-submodular set functions

Cites Work

• Unnamed Item
• Unnamed Item
• A framework of discrete DC programming by discrete convex analysis
• A note on maximizing a submodular set function subject to a knapsack constraint
• Solving the degree-concentrated fault-tolerant spanning subgraph problem by DC programming
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• Parametric monotone function maximization with matroid constraints
• Maximize a monotone function with a generic submodularity ratio
• Set function 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
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
• Fast algorithms for maximizing submodular functions

This page was built for publication: Fast algorithms for maximizing monotone nonsubmodular functions