Embracing the giant component Export

@article{citeulike:1300654, abstract = {Consider a game in which edges of a graph are provided a pair at a time, and the player selects one edge from each pair, attempting to construct a graph with a component as large as possible. This game is in the spirit of recent papers on avoiding a giant component, but here we embrace it. We analyze this game in the offline and online setting, for arbitrary and random instances, which provides for interesting comparisons. For arbitrary instances, we find that the competitive ratio (the best possible solution value divided by best possible online solution value) is large. For ?sparse? random instances the competitive ratio is also large, with high probability (whp); If the instance has ¼(1 + \ϵ)n random edge pairs, with 0 \< \ϵ ? 0.003, then any online algorithm generates a component of size O((log n)3/2) whp, while the optimal offline solution contains a component of size \&OHgr;(n) whp. For ?dense? random instances, the average-case competitive ratio is much smaller. If the instance has ½(1 - \ϵ)n random edge pairs, with 0 \< \ϵ ? 0.015, we give an online algorithm which finds a component of size \&OHgr;(n) whp. {\copyright} 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005}, address = {Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213; Department of Mathematical Sciences, IBM T.J. Watson Research Center, Yorktown Heights, New York 10598}, author = {Flaxman, Abraham D. and Gamarnik, David and Sorkin, Gregory B.}, citeulike-article-id = {1300654}, citeulike-linkout-0 = {http://dx.doi.org/10.1002/rsa.20070}, citeulike-linkout-1 = {http://www3.interscience.wiley.com/cgi-bin/abstract/110486243/ABSTRACT}, doi = {10.1002/rsa.20070}, journal = {Random Structures and Algorithms}, keywords = {achlioptas, algorithms, component, giant, graphs, online, process, random, threshold}, number = {3}, pages = {277--289}, posted-at = {2007-05-16 19:43:12}, priority = {0}, title = {Embracing the giant component}, url = {http://dx.doi.org/10.1002/rsa.20070}, volume = {27}, year = {2005} }

TY - JOUR ID - citeulike:1300654 L3 - citeulike-article-id:1300654 N2 - Consider a game in which edges of a graph are provided a pair at a time, and the player selects one edge from each pair, attempting to construct a graph with a component as large as possible. This game is in the spirit of recent papers on avoiding a giant component, but here we embrace it. We analyze this game in the offline and online setting, for arbitrary and random instances, which provides for interesting comparisons. For arbitrary instances, we find that the competitive ratio (the best possible solution value divided by best possible online solution value) is large. For ?sparse? random instances the competitive ratio is also large, with high probability (whp); If the instance has ¼(1 + ϵ)n random edge pairs, with 0 < ϵ ? 0.003, then any online algorithm generates a component of size O((log n)3/2) whp, while the optimal offline solution contains a component of size &OHgr;(n) whp. For ?dense? random instances, the average-case competitive ratio is much smaller. If the instance has ½(1 - ϵ)n random edge pairs, with 0 < ϵ ? 0.015, we give an online algorithm which finds a component of size &OHgr;(n) whp. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005 IS - 3 JF - Random Structures and Algorithms AD - Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213; Department of Mathematical Sciences, IBM T.J. Watson Research Center, Yorktown Heights, New York 10598 EP - 289 TI - Embracing the giant component VL - 27 SP - 277 KW - achlioptas KW - algorithms KW - component KW - giant KW - graphs KW - online KW - process KW - random KW - threshold AU - Flaxman, Abraham AU - Gamarnik, David AU - Sorkin, Gregory PY - 2005/// UR - http://dx.doi.org/10.1002/rsa.20070 ER -