ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS
From MaRDI portal
Publication:3634201
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
- A Note on Kelso and Crawford's Gross Substitutes Condition
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- A note on maximizing a submodular set function subject to a knapsack constraint
- An analysis of approximations for maximizing submodular set functions—I
- Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
- Combinatorial auctions with decreasing marginal utilities
- Convexity and Steinitz's exchange property
- Discrete Convex Analysis
- Extension of M-convexity and L-convexity to polyhedral convex functions
- Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem.
- Generalized polymatroids and submodular flows
- New characterizations of M-convex functions and their applications to economic equilibrium models with indivisibilities.
- Pipage rounding: a new method of constructing algorithms with proven performance guarantee
- Submodular functions and optimization.
- 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
- The ellipsoid method and its consequences in combinatorial optimization
- Valuated Matroid Intersection I: Optimality Criteria
- \(M\)-convex function on generalized polymatroid
Cited in
(11)- Recent developments in discrete convex analysis
- A new approximation guarantee for monotone submodular function maximization via discrete convexity
- Streaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer lattice
- Matroid rank functions and discrete concavity
- On the correlation gap of matroids
- Polynomial-time approximation schemes for maximizing gross substitutes utility under budget constraints
- Streaming algorithms for non-submodular functions maximization with \(d\)-knapsack constraint on the Integer lattice
- Maximization of monotone non-submodular functions with a knapsack constraint over the integer lattice
- New dominating sets in social networks
- The finite matroid-based valuation conjecture is false
- Buyback problem with discrete concave valuation functions
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)
