ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS
From MaRDI portal
Publication:3634201
DOI10.1142/S1793830909000063zbMath1192.90184MaRDI QIDQ3634201
Publication date: 23 June 2009
Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)
Related Items
Maximization of monotone non-submodular functions with a knapsack constraint over the integer lattice, New dominating sets in social networks, Matroid rank functions and discrete concavity, On the correlation gap of matroids, Unnamed Item, Recent Developments in Discrete Convex Analysis, Buyback problem with discrete concave valuation functions, The Finite Matroid-Based Valuation Conjecture is False, Maximizing monotone submodular functions over the integer lattice, Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility Under Budget Constraints, Streaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer lattice
Cites Work
- Convexity and Steinitz's exchange property
- Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
- Testing membership in matroid polyhedra
- Generalized polymatroids and submodular flows
- The ellipsoid method and its consequences in combinatorial optimization
- New characterizations of M-convex functions and their applications to economic equilibrium models with indivisibilities.
- Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem.
- A note on maximizing a submodular set function subject to a knapsack constraint
- Extension of M-convexity and L-convexity to polyhedral convex functions
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
- Pipage rounding: a new method of constructing algorithms with proven performance guarantee
- Combinatorial auctions with decreasing marginal utilities
- Submodular functions and optimization.
- M-Convex Function on Generalized Polymatroid
- A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
- An analysis of approximations for maximizing submodular set functions—I
- Discrete Convex Analysis
- Valuated Matroid Intersection I: Optimality Criteria
- A Note on Kelso and Crawford's Gross Substitutes Condition
