TY - GEN

T1 - Online matroid intersection

T2 - 19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017

AU - Guruganesh, Guru Prashanth

AU - Singla, Sahil

N1 - Funding Information:
Supported in part by NSF awards CCF-1319811, CCF-1536002, and CCF-1617790.
Publisher Copyright:
© Springer International Publishing AG 2017.

PY - 2017

Y1 - 2017

N2 - For two matroids M1 and M2 defined on the same ground set E, the online matroid intersection problem is to design an algorithm that constructs a large common independent set in an online fashion. The algorithm is presented with the ground set elements one-by-one in a uniformly random order. At each step, the algorithm must irrevocably decide whether to pick the element, while always maintaining a common independent set. While the natural greedy algorithm—pick an element whenever possible—is half competitive, nothing better was previously known; even for the special case of online bipartite matching in the edge arrival model. We present the first randomized online algorithm that has a12 + δ competitive ratio in expectation, where δ > 0 is a constant. The expectation is over the random order and the coin tosses of the algorithm. As a corollary, we also obtain the first linear time algorithm that beats half competitiveness for offline matroid intersection.

AB - For two matroids M1 and M2 defined on the same ground set E, the online matroid intersection problem is to design an algorithm that constructs a large common independent set in an online fashion. The algorithm is presented with the ground set elements one-by-one in a uniformly random order. At each step, the algorithm must irrevocably decide whether to pick the element, while always maintaining a common independent set. While the natural greedy algorithm—pick an element whenever possible—is half competitive, nothing better was previously known; even for the special case of online bipartite matching in the edge arrival model. We present the first randomized online algorithm that has a12 + δ competitive ratio in expectation, where δ > 0 is a constant. The expectation is over the random order and the coin tosses of the algorithm. As a corollary, we also obtain the first linear time algorithm that beats half competitiveness for offline matroid intersection.

KW - Competitive analysis

KW - Linear-time algorithms

KW - Matroid intersection

KW - Online algorithms

KW - Randomized algorithms

UR - http://www.scopus.com/inward/record.url?scp=85020524937&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85020524937&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-59250-3_20

DO - 10.1007/978-3-319-59250-3_20

M3 - Conference contribution

AN - SCOPUS:85020524937

SN - 9783319592497

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 241

EP - 253

BT - Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Proceedings

A2 - Eisenbrand, Friedrich

A2 - Koenemann, Jochen

PB - Springer Verlag

Y2 - 26 June 2017 through 28 June 2017

ER -