




















 
Notes:
In this paper we use Talagrand's inequality to prove a concentration inequality for Lipschitz,
monotone submodular functions.
We were unaware of prior work proving concentration for subadditive functions by
Schechtman in 2003, using Talagrand's inequality,
and by Hajiaghayi et al. in 2005, using selfbounding functions.
In 2009, Chekuri and Vondrak also proved a concentration inequality for Lipschitz, monotone submodular functions, using the FKG inequality. Their inequality achieves Chernofftype concentration, which is somewhat better than the Talagrandlike concentration that we achieve. An earlier version of our paper only proved concentration for matroid rank functions. After learning of the work of Chekuri and Vondrak, we improved our inequality to its current form, in which it applies to arbitrary Lipschitz, monotone, submodular functions. Perhaps the nicest way to prove such inequalities is using selfbounding functions. In particular, this approach yields concentration for nonmonotone functions; it is not clear whether the FKG or Talagrand approaches do too. See the note by Vondrak from 2010. 
 
Notes: Many of the results in this paper were independently discovered by Fung & Harvey and by Hariharan & Panigrahi. Actually Hariharan & Panigrahi had many more algorithmic results than we did, including the linear time algorithm for unweighted graphs. They graciously offered to merge the papers for a joint STOC submission. 



 
Notes: The abstract is somewhat misleading. For matroids of rank 1, there is a trivial lower bound of 2n2 queries. Another trivial argument gives a lower bound of n queries for matroids of rank n/2. The matroids in this paper also have rank n/2, but our lower bound is roughly 1.58n queries. 




 
Notes: I recommend reading the journal version of this paper, not the conference version. The algorithms in the journal version are different and simpler. The conference paper sketched algorithms for the basic pathmatching and independent matching problems. To keep the journal paper as simple as possible, these are not discussed there. The conference papers also claims that graphic matroid intersection can be solved in O(n^{2.575}) time. When asked to provide the details, I could not reproduce them. Most likely I was mistaken, so I retract the claim. 



 
Notes: Very similar results were independently obtained in Jain, Vazirani, Yuval. "On the capacity of multiple unicast sessions in undirected graphs". IEEE/ACM Transactions on Networking, 2006. The paper in SODA is a merge of these two papers, plus additional results obtained with Micah Adler. 


 
Notes:
After this research was done, we discovered that a deterministic algorithm for network coding multicast had already been obtained in Jaggi, Sanders, Chou, Effros, Egner, Jain, and Tolhuizen. "Polynomial time algorithms for multicast network code construction", IEEE Transactions on Information Theory 2005. Their algorithm is quite a bit simpler, especially if you're not familiar with matroids.
My master's thesis is an extended version of this work, containing a much more detailed explanation than the conference version. 


 
Notes: After writing the initial version of this paper, we discovered that an implicit data structure with better runtime bounds had been obtained 15 years earlier in S. Carlsson, J. I. Munro, and P. V. Poblete. "An implicit binomial queue with constant insertion time". SWAT 1988, 113. Our structure is somewhat simpler since we only implement a binary heap, not a binomial queue. 
 
Notes: A related and simpler design can be found in Goodrich, Nelson, and Sun. "The rainbow skip graph: A faulttolerant constantdegree distributed data structure", SODA 2006. 

 
Notes: The analysis of our algorithm ASM2 is due to David Bruce Wilson. A much nicer algorithm for the Optimal Semi Matching problem appears in Jittat Fakcharoenphol, Bundit Laekhanukit, Danupon Nanongkai. "Faster Algorithms for SemiMatching Problems", ICALP 2010. 
 
Notes: Essentially the same idea was independently discovered by Aspnes and Shah, and published in James Aspnes, Gauri Shah, "Skip graphs". SODA 2003, 384393. 
