Fetching the paper…
Reading the bibliography…
Motivated by several applications, we consider the problem of randomly rounding a fractional solution in a matroid (base) polytope to an integral one.
Matroids, submodular functions and certain polyhedra
J. Edmonds · 1970
Earlier work this paper cites.
An analysis of approximations for maximizing submodular set functions - II
M. L. Fisher, G. L. Nemhauser and L. A. Wolsey · 1978
Earlier work this paper cites.
An analysis of approximations for maximizing submodular set functions - I
G. L. Nemhauser, L. A. Wolsey and M. L. Fisher · 1978
Earlier work this paper cites.
Best algorithms for approximating the maximum of a submodular set function
G. L. Nemhauser and L. A. Wolsey · 1978
Earlier work this paper cites.
Testing membership in matroid polyhedra
W. H. Cunningham · 1984
Earlier work this paper cites.
Randomized rounding: a technique for provably good algorithms and algorithmic proofs
P. Raghavan and C. D. Thompson · 1987
Earlier work this paper cites.
Random pseudo-polynomial algorithms for exact matroid problems
P.M. Camerini, G. Galbiati, and F. Maffioli · 1992
Earlier work this paper cites.
Combinatorial Geometry
J. Pach and P. K. Agarwal · 1995
Earlier work this paper cites.
An extension of the Lovász Local Lemma, and its applications to integer programming
A. Srinivasan · 1996
Earlier work this paper cites.
Randomized distributed edge coloring via an extension of the Chernoff-Hoeffding bounds
A. Panconesi and A. Srinivasan · 1997
Earlier work this paper cites.
A threshold of ln n \ln n for approximating set cover
U. Feige · 1998
Earlier work this paper cites.
Packing algorithms for arborescences (and spanning trees) in capacitated graphs
H.N. Gabow and K.S. Manu · 1998
Earlier work this paper cites.
Theory of Linear and Integer Programming
A. Schrijver · 1998
Cited alongside, same era.
The complexity of tradeoffs, and optimal access of web sources
C. H. Papadimitriou and M. Yannakakis · 2000
Cited alongside, same era.
New algorithmic aspects of the local lemma with applications to routing and partitioning
T. Leighton, C.-J.Lu, S. Rao, and A. Srinivasan · 2001
Cited alongside, same era.
Distributions on level-sets with applications to approximation algorithms,
A. Srinivasan · 2001
Cited alongside, same era.
Combinatorial optimization - polyhedra and efficiency
A. Schrijver · 2003
Cited alongside, same era.
Pipage rounding: a new method of constructing algorithms with proven performance guarantee
A. Ageev and M. Sviridenko · 2004
Cited alongside, same era.
Approximating minimum bounded degree spanning tress to within one of optimal,
M. Singh and L.C. Lau · 2007
Later among the works it cites.
Maximizing a submodular set function subject to a matroid constraint
G. Calinescu, C. Chekuri, M. Pál and J. Vondrák · 2008
Later among the works it cites.
Degree bounded matroids and submodular flows
T. Király, L. C. Lau, and M. Singh · 2008
Later among the works it cites.
Optimal approximation for the submodular welfare problem in the value oracle model
J. Vondrák · 2008
Later among the works it cites.
Personal communication, 2009
A. Gupta, V. Nagarajan and R. Ravi · 2009
Closest in time.
Maximizing submodular set functions subject to multiple linear constraints
A. Kulik, H. Shachnai and T. Tamir · 2009
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
On the Crossing Spanning Tree Problem
V. Bilo, V. Goyal, R. Ravi and M. Singh · 2004
Cited alongside, same era.
Minimizing the stabbing number of matchings, trees, and triangulations
S. P. Fekete, M. E. Lübbecke and H. Meijer · 2004
Cited alongside, same era.
Dependent rounding and its applications to approximation algorithms
R. Gandhi, S. Khuller, S. Parthasarathy and A. Srinivasan · 2006
Cited alongside, same era.
Combinatorial auctions with decreasing marginal utilities
B. Lehmann, D. J. Lehmann, and N. Nisan · 2006
Cited alongside, same era.
Maximizing a submodular set function subject to a matroid constraint
G. Calinescu, C. Chekuri, M. Pál and J. Vondrák · 2007
Cited alongside, same era.
The Probabilistic Method
N. Alon and J. Spencer
Cited in the paper.
A Unified Approach to Scheduling on Unrelated Parallel Machines
V. S. A. Kumar, M. V. Marathe, S. Parthasarathy and A. Srinivasan · 2009
Closest in time.
Maximizing non-monotone submodular functions under matroid and knapsack constraints
J. Lee, V. Mirrokni, V. Nagarajan and M. Sviridenko · 2009
Closest in time.
Submodular maximization over multiple matroids via generalized exchange properties
J. Lee, M. Sviridenko, and J. Vondrák · 2009
Closest in time.
Symmetry and approximability of submodular maximization problems
J. Vondrák · 2009
Closest in time.
An O ( log n / log log n ) O(\log n/\log\log n) -approximation algorithm for the assymetric traveling salesman problem
A. Asadpour, M. Goemans, A. Madry, S.O. Gharan, and A. Saberi · 2010
Closest in time.