A note on maximizing a submodular set function subject to a knapsack constraint

DOI10.1016/S0167-6377(03)00062-2zbMath1056.90124OpenAlexW2033885045MaRDI QIDQ1433658

Publication date: 1 July 2004

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0167-6377(03)00062-2

zbMATH Keywords

Approximation algorithm Submodular function

Mathematics Subject Classification ID

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

Related Items (only showing first 100 items - show all)

Strategyproof mechanisms for competitive influence in networks ⋮ Packing Under Convex Quadratic Constraints ⋮ Dual domination problems in graphs ⋮ An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model ⋮ Multiple knapsack-constrained monotone DR-submodular maximization on distributive lattice -- continuous greedy algorithm on median complex -- ⋮ Two-stage stochastic max-weight independent set problems ⋮ Maximization of monotone non-submodular functions with a knapsack constraint over the integer lattice ⋮ A multi-pass streaming algorithm for regularized submodular maximization ⋮ Measured continuous greedy with differential privacy ⋮ Robust Monotone Submodular Function Maximization ⋮ Maximizing a non-decreasing non-submodular function subject to various types of constraints ⋮ Maximizing a monotone non-submodular function under a knapsack constraint ⋮ C2IM: community based context-aware influence maximization in social networks ⋮ Fractional 0-1 programming and submodularity ⋮ Algorithms for covering multiple submodular constraints and applications ⋮ Maximizing \(k\)-submodular functions under budget constraint: applications and streaming algorithms ⋮ Structured Robust Submodular Maximization: Offline and Online Algorithms ⋮ Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization ⋮ Decision trees for function evaluation: simultaneous optimization of worst and expected cost ⋮ Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint ⋮ On maximizing a monotone \(k\)-submodular function under a knapsack constraint ⋮ FPT approximation schemes for maximizing submodular functions ⋮ Discrete Stochastic Submodular Maximization: Adaptive vs. Non-adaptive vs. Offline ⋮ Optimization with demand oracles ⋮ An accelerated continuous greedy algorithm for maximizing strong submodular functions ⋮ The knapsack problem with neighbour constraints ⋮ Thresholded covering algorithms for robust and max-min optimization ⋮ A fast and deterministic algorithm for knapsack-constrained monotone DR-submodular maximization over an integer lattice ⋮ Simple and efficient budget feasible mechanisms for monotone submodular valuations ⋮ Streaming algorithm for maximizing a monotone non-submodular function under \(d\)-knapsack constraint ⋮ Constrained Submodular Maximization via a Nonsymmetric Technique ⋮ Submodular Maximization Through the Lens of Linear Programming ⋮ Streaming submodular maximization under \(d\)-knapsack constraints ⋮ Submodular optimization problems and greedy strategies: a survey ⋮ Unnamed Item ⋮ Optimizing node discovery on networks: problem definitions, fast algorithms, and observations ⋮ The multi-budget maximum weighted coverage problem ⋮ A simple deterministic algorithm for symmetric submodular maximization subject to a knapsack constraint ⋮ Tight Approximation Bounds for the Seminar Assignment Problem ⋮ On maximizing monotone or non-monotone \(k\)-submodular functions with the intersection of knapsack and matroid constraints ⋮ Recent Developments in Discrete Convex Analysis ⋮ Practical budgeted submodular maximization ⋮ Per-Round Knapsack-Constrained Linear Submodular Bandits ⋮ Formulations and Approximation Algorithms for Multilevel Uncapacitated Facility Location ⋮ Maximize a monotone function with a generic submodularity ratio ⋮ Primal-dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approach ⋮ Budgeted nature reserve selection with diversity feature loss and arbitrary split systems ⋮ Cut problems in graphs with a budget constraint ⋮ Influence Maximization in Social Networks ⋮ Online budgeted maximum coverage ⋮ A two-stage stochastic programming approach for influence maximization in social networks ⋮ Approximation algorithms for the robust/soft-capacitated 2-level facility location problems ⋮ Supermodular covering knapsack polytope ⋮ On maximizing a monotone \(k\)-submodular function subject to a matroid constraint ⋮ New performance guarantees for the greedy maximization of submodular set functions ⋮ Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint ⋮ Unnamed Item ⋮ Video distribution under multiple constraints ⋮ Algorithms for storage allocation based on client preferences ⋮ Unnamed Item ⋮ Non-monotone submodular function maximization under \(k\)-system constraint ⋮ A continuous knapsack problem with separable convex utilities: approximation algorithms and applications ⋮ Risk averse submodular utility maximization ⋮ Maximizing expected utility over a knapsack constraint ⋮ A random algorithm for profit maximization in online social networks ⋮ Non-submodular streaming maximization with minimum memory and low adaptive complexity ⋮ Robust monotone submodular function maximization ⋮ Maximizing monotone submodular functions over the integer lattice ⋮ Constrained submodular maximization via greedy local search ⋮ Maximum Betweenness Centrality: Approximability and Tractable Cases ⋮ Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint ⋮ A fast double greedy algorithm for non-monotone DR-submodular function maximization ⋮ Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint ⋮ Generalized budgeted submodular set function maximization ⋮ Budget Feasible Procurement Auctions ⋮ ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS ⋮ A refined analysis of submodular greedy ⋮ A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint ⋮ Worst-Case Mechanism Design via Bayesian Analysis ⋮ A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints ⋮ Set function optimization ⋮ Submodular Maximization with Uncertain Knapsack Capacity ⋮ Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint ⋮ An almost optimal approximation algorithm for monotone submodular multiple knapsack ⋮ On social envy-freeness in multi-unit markets ⋮ Multi-pass streaming algorithms for monotone submodular function maximization ⋮ The submodular knapsack polytope ⋮ Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility Under Budget Constraints ⋮ Fractionally subadditive maximization under an incremental knapsack constraint ⋮ Streaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer lattice ⋮ Submodular maximization of concave utility functions composed with a set-union operator with applications to maximal covering location problems ⋮ Approximation algorithms for fragmenting a graph against a stochastically-located threat ⋮ Unnamed Item ⋮ Budget-Feasible Mechanism Design for Non-monotone Submodular Objectives: Offline and Online ⋮ Non-Submodular Maximization with Matroid and Knapsack Constraints ⋮ Streaming Algorithms for Maximizing Monotone DR-Submodular Functions with a Cardinality Constraint on the Integer Lattice ⋮ Tight Approximation for Unconstrained XOS Maximization ⋮ Maximum coverage with cluster constraints: an LP-based approximation technique ⋮ An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint ⋮ Packing under convex quadratic constraints

Cites Work

This page was built for publication: A note on maximizing a submodular set function subject to a knapsack constraint