%% ToC#231  v002/a012.bib  A. Deshpande, L. Rademacher, S. Vempala, G. Wang

@techreport{RVW,
 author = {L. Rademacher and S. Vempala and G. Wang},
 title = {Matrix Approximation and Projective Clustering},
 institution = {MIT CSAIL},
 type="Technical Report",
 number="2005--018",
 year = {2005}}

@inproceedings{DRVW,
 author = {A. Deshpande and L. Rademacher and S. Vempala and G. Wang},
 title = {Matrix Approximation and Projective Clustering via Volume Sampling},
 booktitle = {Proc. 17th ACM-SIAM Symp. on Discrete Algorithms (SODA'06)},
 publisher = {SIAM},
 year = 2006,
 pages = {1117--1126},
 eprint="soda:1109557.1109681"}

@inproceedings{DV,
 author = {A. Deshpande and S. Vempala},
 title = {Adaptive Sampling and Fast Low-Rank Matrix Approximation},
 booktitle = {Proc. 10th Internat. Workshop on Randomization and Computation (RANDOM'06)},
 publisher = {Springer},
 year = 2006,
 pages = {292--303},
 pdf="http://web.mit.edu/amitd/www/academics/random06.pdf"}

@InProceedings{AM,
 author = {D. Achlioptas and F. McSherry},
 title = {Fast Computation of Low Rank Matrix Approximations},
 booktitle = {Proc. 33rd STOC.},
 year = {2001},
 pages = {611--618},
 publisher = {ACM Press},
 eprint="stoc:380752.380858"
}

@article{APV,
 author = {P. Agarwal and C. Procopiuc and K. Varadarajan},
 title = {Approximation Algorithms for a $k$-line center},
 journal = {Algorithmica},
 volume = {42},
 issue = {3--4},
 year = {2005},
 pages = {221--230},
 eprint="algorithmica:p321725768012505"}

@article{AHV,
 author = {P. Agarwal and S. Har-Peled and K. Varadarajan},
 title = {Geometric Approximations via Coresets},
 journal = {Combinatorial and Computational Geometry - MSRI Publications},
 publisher = {Cambridge University Press},
 pages = {1--30},
 volume = {52},
 year = 2005,
 pdf="http://valis.cs.uiuc.edu/~sariel/papers/04/survey/survey.pdf"}

@InProceedings{AgMu,
 author = {P. Agarwal and N. Mustafa},
 title = {$k$-Means Projective Clustering},
 booktitle = {Proc. Principles of Database Systems (PODS'04)},
 publisher = {ACM Press},
 year = {2004},
 pages = {155--165},
 eprint="pods:1055558.1055581"}

@article{AGGR,
 author = {R. Agarwal and J. Gehrke and D. Gunopulos and P. Raghavan},
 title = {Automatic subspace clustering of high dimensional data for data
 mining applications},
 journal = {Data Mining and Knowledge Discovery},
 volume = {11},
 pages = {5--33},
 year = 2005,
 issue = 1,
 eprint="Springer:m18077t9134v55n2"}

@InProceedings{APWYP,
  author = {C. Aggarwal and C. Procopiuc and J. Wolf and  P. Yu and J. Park},
  title = {Fast Algorithms for Projected Clustering},
  booktitle = {Proc. Conf. on Management of Data (SIGMOD'99)},
  publisher = {ACM Press},
  year = {1999},
  pages = {61--72},
  eprint="sigmod:304182.304188"}

@article{AMS,
 author = {N. Alon and Y. Matias and M. Szegedy},
 title = {The space complexity of approximating the frequency moments},
 journal = {J. Computer and System Sciences},
 year = {1999},
 volume = {58},
 issue = {1},
 pages = {137--147},
 eprint="jcss:10.1006/jcss.1997.1545"}

@book{Ar,
 author = {M. Artin},
 title = {Algebra},
 publisher = {Prentice-Hall},
 year = {1991}}

@InProceedings{BHI,
 author = {M. B\u{a}doiu and S. Har-Peled and P. Indyk},
 title = {Approximate Clustering via Core-Sets},
 booktitle = {Proc. 34th STOC.},
 publisher = {ACM Press},
 year = {2002},
 pages = {250--257},
 eprint="stoc:509907.509947"
}

@InProceedings{Bar,
 author = {Z. Bar-Yossef},
 title = {Sampling Lower Bounds via Information Theory},
 booktitle = {Proc. 35th STOC.},
 publisher = {ACM Press},
 year = {2003},
 pages = {335--344},
 eprint="stoc:780542.780593"}

@InProceedings{FKKR,
 author = {W. Fernandez~de~la~Vega and M. Karpinski and C. Kenyon and Y. Rabani},
 title = {Approximation schemes for clustering problems},
 booktitle = {Proc. 35th STOC.},
 publisher = {ACM Press},
 year = {2003},
 pages = {50--58},
 eprint="stoc:780542.780550"}

@article{DFKVV,
 author = {P. Drineas and R. Kannan and A. Frieze and S. Vempala and V. Vinay},
 title = {Clustering large graphs via the Singular Value Decomposition},
 journal = {Machine Learning},
 volume = 56,
 pages = {9--33},
 year = {2004},
 eprint="ml:u424k6nn6k622788"}

@InProceedings{DK,
 author = {P. Drineas and R. Kannan},
 title = {Pass Efficient Algorithms for approximating large matrices},
 booktitle = {Proc. 14th ACM-SIAM Symp. on Discrete Algorithms (SODA'03)},
 publisher = {SIAM},
 pages = {223--232},
 year = {2003},
 eprint="soda:644108.644147"}

@article{DKM,
 author = {P. Drineas and R. Kannan and M. Mahoney},
 title = {Fast {M}onte {C}arlo Algorithms for Matrices {II}: Computing a Low-Rank Approximation to a Matrix},
 journal = {SIAM J. on Computing},
 volume = 36,
 issue = 1,
 pages = {158--183},
 year =  {2006},
 eprint="sicomp:10.1137/S0097539704442696"}

@InProceedings{ES,
 author = {M. Effros and L. J. Schulman},
 title = {Rapid near-optimal {VQ} design with a deterministic data net},
 booktitle = {Proc. Int. Symp. on Information Theory},
 publisher = {IEEE},
 year = {2004},
 pages="298",
 eprint="isit:10.1109/ISIT.2004.1365336"}

@article{FKMSZ,
 author = {J. Feigenbaum and S. Kannan and A. McGregor and S. Suri and J. Zhang.},
 title = {On Graph Problems in a Semi-Streaming Model},
 journal = {Theoretical Computer Science},
 volume = 348,
 issue = 2,
 pages = {207--216},
 year = {2005},
 eprint="tcs:10.1016/j.tcs.2005.09.013"}

@article{FKV,
 author = {A. Frieze and R. Kannan and S. Vempala},
 title = {Fast {M}onte {C}arlo algorithms for finding low-rank approximations},
 journal = {Journal of the ACM},
 year = {2004},
 volume = {51},
 issue = {6},
 pages = {1025--1041},
 eprint="jacm:1039488.1039494"}

@book{GVL,
 author = {G. H. Golub and C. F. van Loan},
 title = {Matrix Computations},
 edition = {Third},
 publisher = {Johns Hopkins},
 year = {1996}}

@article{GT,
 author = {S. A. Goreinov and E. E. Tyrtyshnikov},
 title = {The maximal-volume concept in approximation by low-rank matrices},
 journal = {Contemporary Mathematics},
 volume = 280,
 pages = {47--51},
 year = 2001}

@article{GKS,
 author = {S. Guha and N. Koudas and K. Shim},
 title = {Approximation and streaming algorithms for histogram construction problems},
 journal = {ACM Transactions on Database Systems},
 volume = 31,
 issue = 1,
 pages = {396--438},
 year = {2006},
 eprint="tods:1132863.1132873"}

@InProceedings{HM,
 author = {S. Har-Peled and S. Mazumdar},
 title = {On coresets for $k$-means and $k$-median clustering},
 booktitle = {Proc. 36th STOC.},
 publisher = {ACM Press},
 year = {2004},
 pages = {291--300},
 eprint="stoc:1007352.1007400"}

@InProceedings{HV,
 author = {S. Har-Peled and K. Varadarajan},
 title = {Projective Clustering in High Dimensions using Core-Sets},
 booktitle = {Proc. 18th Symp. on Comp. Geometry (SOCG)},
 publisher = {ACM Press},
 pages = {312--318},
 year = {2002},
 eprint="socg:513400.513440"}

@article{HRR,
 author = {M. Henzinger and P. Raghavan and S. Rajagopalan},
 title = {Computing on Data Streams},
 journal = {External Memory Algorithms -- DIMACS Series in Discrete Mathematics and Computer Science},
 volume = {50},
 year = {1999},
 pages = {107--118}}

@InProceedings{KM,
 author = {D. Kempe and F. McSherry},
 title = {A decentralized algorithm for spectral analysis},
 booktitle = {Proc. 36th STOC.},
 publisher = {ACM Press},
 pages = {561--568},
 year = {2004},
 eprint="stoc:1007352.1007438"}

@article{KW,
 author = {J. Kuczy\'{n}ski and H. Wo\'{z}niakowski},
 title =  {Estimating the largest eigenvalues by the power and {L}anczos algorithms with a random start},
 journal = {SIAM J. Matrix Anal.  Appl.},
 volume = {13},
 issue = {4},
 pages = {1094--1122},
 year = {1992},
 eprint="simax:10.1137/0613066"}

@InProceedings{KSS,
 author = {A. Kumar and Y. Sabharwal and S. Sen.},
 title = {A simple linear time $(1+\epsilon)$-approximation algorithm for $k$-means clustering in any
 dimensions},
 booktitle = {Proc. 45th FOCS},
 publisher = {IEEE Computer Society Press},
 year = {2004},
 pages = {454--462},
 eprint="focs:10.1109/FOCS.2004.7"}

@article{M,
 author = {J. Matou\v{s}ek},
 title = {On approximate geometric $k$-clustering},
 journal = {Discrete and Computational Geometry},
 volume = {24},
 issue = {1},
 pages = {61--84},
 year = {2000},
 eprint="Springer:xawxbau59gtjtvv6"}

@article{MT,
 author = {N. Megiddo and A. Tamir},
 title = {On the complexity of locating linear facilities in the plane},
 journal = {Operations Research Letters},
 volume = {13},
 pages = {194--197},
 year = {1982},
 eprint="Elsevier:10.1016/0167-6377(82)90039-6"}

@article{OR,
 author = {R. Ostrovsky and Y. Rabani},
 title = {Polynomial time approximation schemes for geometric min-sum median clustering},
 journal = {Journal of the ACM},
 volume = {49},
 issue = {2},
 year = {2002},
 pages = {139--156},
 eprint="jacm:506147.506149"}

@InProceedings{PJAM,
 author = {C. Procopiuc and P. Agarwal and T. Murali and M. Jones},
 title = {A {M}onte {C}arlo Algorithm for Fast Projective clustering},
 booktitle = {Proc. Conf. on Management of Data (SIGMOD'02)},
 publisher = {ACM Press},
 pages = {418--427},
 year = 2002,
 eprint="sigmod:564691.564739"}

@InProceedings{S,
 author = {T. Sarl\'os},
 title = {Improved approximation algorithms for large matrices via random projection},
 booktitle = {Proc. 47th FOCS},
 publisher = {IEEE Computer Society Press},
 pages = {143-152},
 year = {2006},
 pdf="http://www.ilab.sztaki.hu/%7Estamas/publications/rp.pdf"}