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 - 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 - https://www.scopus.com/pages/publications/85020524937
UR - https://www.scopus.com/pages/publications/85020524937#tab=citedBy
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 -