Tue, Thu
2:50-4:05 PM
LSRC D243
Course CPS296.2  Spring 2007
Reading

Books and Lecture Notes

  1. S. Har-Peled, Geometric Approximation Algorithms, Department of Computer Science, UIUC, 2006.
  2. J.-R. Sack and J. Urrutia (eds.), Handbook of Computational Geometry. North-Holland, 2000.
  3. J. E. Goodman and J. O'Rourke (eds.), Handbook of Discrete and Computational Geometry, 2nd edition, CRC Press LLC, Boca Raton, FL, 2004.
  4. J. Matoušek, Lectures on Discerete Geometry, Springer, Heidelberg, 2002.
  5. R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.
  6. B. Chazelle. The Discrepancy Method: Randomness and Complexity. Cambridge University Press, 2000.

Survey Papers

  1. S. Arora, Approximation schemes for NP-hard geometric optimization problems: A survey, Math Programming, 97, 2003.
  2. M. Goldwasser, A survey of linear programming in randomized subexponential time, SIGACT News, 26 (1995), 96-104.
  3. P. K. Agarwal and M. Sharir, Efficient algorithms for geometric optimization. ACM Comput. Surv. 30:412-458, 1998.
  4. P. K. Agarwal, S. Har-Peled, and K. R. Varadarajan, Geometric approximation via coresets, in Combinatorial and Computational Geometry (J. E. Goodman, J. Pach, and E. Welzl, eds.), Cambridge University Press, New York, 2005, 1-30.
  5. B. Gärtner and E. Welzl, Linear programming randomization and abstract frameworks, Proc. 13th Ann. Symp. on Theoret. Aspects of Comput. Sci., 1996, 669-687.

Linear Programming

  1. T. Terlaky, An easy way to teach interior-point methods, European J. Operations Research, 130 (2001), 1-19.
  2. M. Grötschel, L. Lovász, and L. Schrijver, Geometric Algorithms and Combinatorial Optimization, 2nd ed., Springer, Heidelberg, 1994.
  3. F. A. Potra and S. J. Wright, Interior-point methods, J. Comput. Appl. Math. 124 (2000), 281-302.
  4. K. L. Clarkson, Las Vegas algorithms for linear and integer programming when the dimension is small, J. ACM 42(2):488-499, 1995.
  5. G. B. Dantzig, Linear Programming, (Historical Account), www2.informs.org/History/ dantzig/LinearProgramming_article.pdf .
  6. L. Lovász, Semidefinite programs and combinatorial optimization, in Recent Advances in Algorithms and Combinatorics (B. Reed and C. Linhares-Sales, eds.), Springer, New York, 2003, 137-194. (Lecture Notes)
  7. R. Seidel, Small-dimensional linear programming and convex hulls made easy, Discrete Comput. Geom. 6(5):423-434, 1991.
  8. D. A. Spielman and S.-H. Teng, Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time, J. ACM 51(3):385-463, 2004
  9. M. J. Todd, The many facets of linear programming, Mathematical Programming 91: 417-436 (2002).
  10. J.A. Kelner and D.A. Spielman, A randomized polynomial-time simplex algorithm for linear programming, STOC '06, 2006, 51-60.

Parametric Searching

  1. N. Megiddo, Applying parallel computation algorithms in the design of serial algorithms, J. ACM, 30 (1983), 852-865.
  2. R. Cole, J. Salowe, W. Steiger, and E. Szemerédi, An optimal-time algorithm for slope selection, SIAM J. Comput., 18 (1989), 792-810.
  3. M. J. Katz and M. Sharir, Optimal slope selection via expanders, Inform. Process. Lett., 47 (1993), 115-122.
  4. J. Matoušek and O. Schwarzkopf, Linear optimization queries, J. Algorithms, 14 (1993), 432-448.
  5. P. K. Agarwal and J. Matoušeku, Ray shooting and parametric search, SIAM J. Comput., 22 (1993), 794-806.

ε-approximations and ε-nets

  1. B. Chazelle, The Discrepancy Method in Computational Geometry, Handbook of Discrete and Computational Geometry, 2nd ed. (J. Goodman and J. O'Rourke, eds), 983-996, CRC Press, 2004.
  2. K.L. Clarkson and P.W. Shor, Applications of random sampling in computational geometry, Discrete Comput. Geom., 4(1989), 387-421.
  3. D.Haussler and E.Welzl, Epsilon-nets and simplex range queries, Discrete Comput. Geom., 2(1987), 127-151.
  4. J.Matoušek, Epsilon-nets and computational geometry, in: New Trends in Discrete and Computational Geometry (J.~Pach, ed.), Algorithms and Combinatorics, , Vol. 10, Springer-Verlag, 1993, pp. 69-89
  5. J. Pach and P. K. Agarwal. Combinatorial Geometry. John Wiley & Sons, New York, NY, 1995.
  6. A. Bagchi, A. Chaudhary, D. Eppstein, and M. Goodrich., Deterministic sampling and range counting in geometric data streams., Proc. 20th Annu. Sympos. Comput. Geom., pages 144-151, 2004.

Core Sets

  1. P.K. Agarwal, S.Har-Peled, and K.R. Varadarajan, Approximating extent measures of points, J. Assoc. Comput. Mach., 51(2004), 606-635.
  2. T.M. Chan, Faster core-set constructions and data stream algorithms in fixed dimensions, Proc. 20th Annu. ACM Sympos. Comput. Geom., 2004, pp.152-159.
  3. G.Barequet and S.Har-Peled, Efficiently approximating the minimum-volume bounding box of a point set in three dimensions, J. Algorithms, 38(2001), 91-109..
  4. H.Yu, P.K. Agarwal, R.Poreddy, and K.R. Varadarajan, Practical methods for shape fitting and kinetic data structures using core sets, Proc. 20th Annu. ACM Sympos. Comput. Geom., 2004, pp.263-272.
  5. P.K. Agarwal, S.Har-Peled, and H.Yu., Robust shape fitting via peeling and grating coresets., Proc. 17th ACM-SIAM Sympos. Discrete Algorithms, pages 182-191, 2006.

Shape Fitting and Clustering

  1. B. Gärtner, A subexponential algorithm for abstract optimization problems, SIAM J. Comput., 24(1995), 1018-1035.
  2. Mihai Badoiu, Kenneth L. Clarkson, Smaller core-sets for balls, SODA, (2003) pp.801-802.
  3. B. Chazelle and J. Matoušek, On linear-time deterministic algorithms for optimization problems in fixed dimension, J. Algorithms, 21(1996), 579-597.
  4. Z. Drezner, The p-centre problems - Heuristic and optimal algorithms, J. Oper. Res. Soc., 35(1984), 741-748.
  5. T. Feder and D.H. Greene, Optimal algorithms for approximate clustering, Proc. 20th Annu. ACM Sympos. Theory Comput., (1988), pp.434-444.
  6. Megiddo and K.J. Supowit, On the complexity of some common geometric location problems, SIAM J. Comput., 13(1984), 182-196.
  7. T. Gonzalez, Clustering to minimize the maximum intercluster distance, Theoret. Comput. Sci., 38(1985), 293-306.
  8. T. Gonzalez, Covering a set of points in multidimensional space, Inform. Process. Lett., 40(1991), 181-188.
  9. M. Badoiu, S. Har-Peled, and P. Indyk Approximate clustering via core-sets, Proc. 34th Annu. ACM Sympos. Theory Comput., (2002), pp.250-257.
  10. S. Har-Peled and S. Mazumdar, Coresets for k-means and k-median clustering and their applications, Proc. 36th Annu. ACM Sympos. Theory Comput., (2004), pp.291-300.
  11. D. Arthur and S. Vassilvitskii, How slow is the k-means method?, Symposium on Computational Geometry, (2006), pp.144-153.
  12. D. Arthur and S. Vassilvitskii, Worst-case and Smoothed Analysis of the ICP Algorithm, with an Application to the k-means Method, FOCS , (2006) pp.153-164.
  13. D. Arthur and S. Vassilvitskii, k-means++: The Advantages of Careful Seeding, SODA '07, (2007).

Geometric Packing and Covering

  1. Jorge Urrutia, Art gallery and illumination problems, In Hanbook on Computational Geometry (J.-R. Sack and J. Urrutia, eds.), North Holland, pp. 387-434, 1997.
  2. V. Chvátal, A greedy heuristic for the set-covering problem, Math. Oper. Res., 4:233-235, 1979.
  3. H. Brönnimann and M.T. Goodrich, Almost optimal set covers in finite VC-dimension, Discrete Comput. Geom., 14:263-279, 1995.
  4. U. Feige, A threshold of ln(n) for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998.
  5. K.L. Clarkson, K.R. Varadarajan, Improved approximation algorithms for geometric set cover, Symposium on Computational Geometry, 2005: 135-141.

Network Design

  1. G. Narasimhan and M. Smid, Geometric Spanning Networks, Cambridge University Press, 2007.
  2. D. Eppstein, Spanning trees and spanners, In Handbook of Computational Geometry (J.-R. Sack and J. Urrutia, eds.), North Holland, pp. 425--461, 1997..