Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs

Awerbuch, 2001, On-line competitive algorithms for call admission in optical networks, Algorithmica, 31, 29, 10.1007/s00453-001-0039-1 Awerbuch, 1994, Competitive non-preemptive call control, 312 Borodin, 1998 Chan, 2003, Polynomial-time approximation schemes for packing and piercing fat objects, J. Algorithms, 46, 178, 10.1016/S0196-6774(02)00294-8 Clark, 1990, Unit disk graphs, Discrete Math., 86, 165, 10.1016/0012-365X(90)90358-O T. Erlebach, J. Fiala. Independence and coloring problems on intersection graphs of disks, Manuscript, 2003. Erlebach, 2001, Polynomial-time approximation schemes for geometric graphs, 671 Hale, 1980, Frequency assignment: theory and applications, Proc. IEEE, 68, 1497, 10.1109/PROC.1980.11899 Halldórsson, 1995, Approximating discrete collections via local improvements, 160 Hliněný, 2001, Representing graphs by disks and balls, Discrete Math., 229, 101, 10.1016/S0012-365X(00)00204-1 Hochbaum, 1983, Efficient bounds for the stable set, vertex cover and set packing problems, Discrete Appl. Math., 6, 243, 10.1016/0166-218X(83)90080-X Hunt III, 1998, NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs, J. Algorithms, 26, 238, 10.1006/jagm.1997.0903 Lipton, 1994, Online interval scheduling, 302 Marathe, 1995, Simple hueristics for unit disk graphs, Networks, 25, 59, 10.1002/net.3230250205 Matsui, 2000, Approximation algorithms for maximum independent set problems and fractional coloring problems on unit disk graphs, vol. 1763, 194 Nieberg, 2004, A robust PTAS for maximum independent sets in unit disk graphs, vol. 2253, 214