ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS
From MaRDI portal
Publication:3634201
DOI10.1142/S1793830909000063zbMATH Open1192.90184MaRDI QIDQ3634201FDOQ3634201
Authors: Akiyoshi Shioura 
Publication date: 23 June 2009
Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)
Recommendations
- Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
- Maximizing a monotone submodular function subject to a matroid constraint
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Submodular function minimization and maximization in discrete convex analysis
Cites Work
- Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
- Discrete Convex Analysis
- The ellipsoid method and its consequences in combinatorial optimization
- Submodular functions and optimization.
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- Combinatorial auctions with decreasing marginal utilities
- A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
- An analysis of approximations for maximizing submodular set functions—I
- Generalized polymatroids and submodular flows
- Testing membership in matroid polyhedra
- A note on maximizing a submodular set function subject to a knapsack constraint
- Pipage rounding: a new method of constructing algorithms with proven performance guarantee
- Convexity and Steinitz's exchange property
- New characterizations of M-convex functions and their applications to economic equilibrium models with indivisibilities.
- \(M\)-convex function on generalized polymatroid
- A Note on Kelso and Crawford's Gross Substitutes Condition
- Extension of M-convexity and L-convexity to polyhedral convex functions
- Valuated Matroid Intersection I: Optimality Criteria
- Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
- Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem.
Cited In (12)
- Buyback problem with discrete concave valuation functions
- The finite matroid-based valuation conjecture is false
- New dominating sets in social networks
- A new approximation guarantee for monotone submodular function maximization via discrete convexity
- On the correlation gap of matroids
- Maximizing monotone submodular functions over the integer lattice
- Polynomial-time approximation schemes for maximizing gross substitutes utility under budget constraints
- Maximization of monotone non-submodular functions with a knapsack constraint over the integer lattice
- Matroid rank functions and discrete concavity
- Streaming algorithms for non-submodular functions maximization with \(d\)-knapsack constraint on the Integer lattice
- Recent developments in discrete convex analysis
- Streaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer lattice
This page was built for publication: ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3634201)
