1. Alon, N., Dar, S., Parnas, M., Ron, D.: Testing of clustering. SIAM Journal on Discrete Mathematics 16(3), 393–417 (2003)

   Article MathSciNet MATH  Google Scholar 

2. Alon, N., Fernandez de la Vega, W., Kannan, R., Karpinski, M.: Random sampling and approximation of MAX-CSPs. Journal of Computer and System Sciences 67(2), 212–243 (2003)

   Article MathSciNet MATH  Google Scholar 

3. Alon, N., Fischer, E., Krivelevich, M., Szegedy, M.: Efficient testing of large graphs. Combinatorica 20(4), 451–476 (2000)

   Article MathSciNet MATH  Google Scholar 

4. Alon, N., Fischer, E., Newman, I., Shapira, A.: A combinatorial characterization of the testable graph properties: it’s all about regularity. SIAM Journal on Computing 39(1), 143–167 (2009)

   Article MathSciNet MATH  Google Scholar 

5. Alon, N., Shapira, A.: Every monotone graph property is testable. SIAM Journal on Computing 38(2), 505–522 (2008)

   Article MathSciNet MATH  Google Scholar 

6. Alon, N., Shapira, A.: A characterization of the (natural) graph properties testable with one-sided error. SIAM Journal on Computing 37(6), 1703–1727 (2008)

   Article MathSciNet MATH  Google Scholar 

7. Alon, N., Shapira, A.: Homomorphisms in graph property testing - A survey. In: Klazar, M., Kratochvil, J., Loebl, M., Matousek, J., Thomas, R., Valtr, P. (eds.) Topics in Discrete Mathematics, dedicated to Jarik Nesetril on the occasion of his 60th Birthday, pp. 281–313

   Google Scholar 

8. Arora, S., Karger, D.R., Karpinski, M.: Polynomial time approximation schemes for dense instances of\(\mathcal{NP}\)-hard problems. Journal of Computer and System Sciences 58(1), 193–210 (1999)

   Article MathSciNet MATH  Google Scholar 

9. Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristics for k-median and facility location problems. SIAM Journal on Computing 33(3), 544–562 (2004)

   Article MathSciNet MATH  Google Scholar 

10. Bădoiu, M., Czumaj, A., Indyk, P., Sohler, C.: Facility location in sublinear time. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 866–877. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

11. Benjamini, I., Schramm, O., Shapira, A.: Every minor-closed property of sparse graphs is testable. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pp. 393–402 (2008)

    Google Scholar 

12. Borgs, C., Chayes, J., Lovász, L., Sos, V.T., Szegedy, B., Vesztergombi, K.: Graph limits and parameter testing. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC) (2006)

    Google Scholar 

13. Charikar, M., O’Callaghan, L., Panigrahy, R.: Better streaming algorithms for clustering problems. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC), pp. 30–39 (2003)

    Google Scholar 

14. Chazelle, B., Dobkin, D.P.: Intersection of convex objects in two and three dimensions. Journal of the ACM 34(1), 1–27 (1987)

    Article MathSciNet  Google Scholar 

15. Chazelle, B., Liu, D., Magen, A.: Sublinear geometric algorithms. SIAM Journal on Computing 35(3), 627–646 (2006)

    Article MathSciNet MATH  Google Scholar 

16. Chazelle, B., Rubinfeld, R., Trevisan, L.: Approximating the minimum spanning tree weight in sublinear time. SIAM Journal on Computing 34(6), 1370–1379 (2005)

    Article MathSciNet MATH  Google Scholar 

17. Chen, K.: Onk-median clustering in high dimensions. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1177–1185 (2006)

    Google Scholar 

18. Czumaj, A., Ergün, F., Fortnow, L., Magen, A., Newman, I., Rubinfeld, R., Sohler, C.: Sublinear-time approximation of Euclidean minimum spanning tree. SIAM Journal on Computing 35(1), 91–109 (2005)

    Article MathSciNet MATH  Google Scholar 

19. Czumaj, A., Shapira, A., Sohler, C.: Testing hereditary properties of non-expanding bounded-degree graphs. SIAM Journal on Computing 38(6), 2499–2510 (2009)

    Article MathSciNet MATH  Google Scholar 

20. Czumaj, A., Sohler, C.: Property testing with geometric queries. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol. 2161, pp. 266–277. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

21. Czumaj, A., Sohler, C.: Estimating the weight of metric minimum spanning trees in sublinear-time. SIAM Journal on Computing 39(3), 904–922 (2009)

    Article MathSciNet MATH  Google Scholar 

22. Czumaj, A., Sohler, C.: Sublinear-time approximation for clustering via random sampling. Random Structures and Algorithms 30(1-2), 226–256 (2007)

    Article MathSciNet MATH  Google Scholar 

23. Czumaj, A., Sohler, C.: Abstract combinatorial programs and efficient property testers. SIAM Journal on Computing, 34(3), 580–615 (2005)

    Article MathSciNet MATH  Google Scholar 

24. Czumaj, A., Sohler, C.: Small space representations for metric min-sumk-clustering and their applications. Theory of Computing Systems 46(3), 416–442 (2010)

    Article MathSciNet MATH  Google Scholar 

25. Czumaj, A., Sohler, C., Ziegler, M.: Property testing in computational geometry. In: Paterson, M. (ed.) ESA 2000. LNCS, vol. 1879, pp. 155–166. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

26. Dyer, M., Megiddo, N., Welzl, E.: Linear programming. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, 2nd edn., pp. 999–1014. CRC Press, Boca Raton (2004)

    Google Scholar 

27. Feige, U.: On sums of independent random variables with unbounded variance and estimating the average degree in a graph. SIAM Journal on Computing 35(4), 964–984 (2006)

    Article MathSciNet MATH  Google Scholar 

28. Fischer, E.: The art of uninformed decisions: A primer to property testing. Bulletin of the EATCS 75, 97–126 (2001)

    MathSciNet MATH  Google Scholar 

29. Frahling, G., Sohler, C.: Coresets in dynamic geometric data streams. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pp. 209–217 (2005)

    Google Scholar 

30. Frieze, A., Kannan, R.: Quick approximation to matrices and applications. Combinatorica 19(2), 175–220 (1999)

    Article MathSciNet MATH  Google Scholar 

31. Frieze, A., Kannan, R., Vempala, S.: Fast Monte-Carlo algorithms for finding low-rank approximations. Journal of the ACM 51(6), 1025–1041 (2004)

    Article MathSciNet MATH  Google Scholar 

32. Goldreich, O.: Combinatorial property testing (a survey). In: Pardalos, P., Rajasekaran, S., Rolim, J. (eds.) Proc. DIMACS Workshop on Randomization Methods in Algorithm Design. DIMACS, Series in Discrete Mathetaics and Theoretical Computer Science, vol. 43, pp. 45–59. American Mathematical Society, Providence (1997)

    Google Scholar 

33. Goldreich, O.: Property testing in massive graphs. In: Abello, J., Pardalos, P.M., Resende, M.G.C. (eds.) Handbook of massive data sets, pp. 123–147. Kluwer Academic Publishers, Dordrecht (2002)

    Chapter  Google Scholar 

34. Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. Journal of the ACM 45(4), 653–750 (1998)

    Article MathSciNet MATH  Google Scholar 

35. Goldreich, O., Ron, D.: Property Testing in Bounded Degree Graphs. Algorithmica 32(2), 302–343 (2002)

    Article MathSciNet MATH  Google Scholar 

36. Goldreich, O., Ron, D.: A sublinear bipartiteness tester for bounded degree graphs. Combinatorica 19(3), 335–373 (1999)

    Article MathSciNet MATH  Google Scholar 

37. Goldreich, O., Ron, D.: Approximating average parameters of graphs. Random Structures and Algorithms 32(4), 473–493 (2008)

    Article MathSciNet MATH  Google Scholar 

38. Har-Peled, S., Mazumdar, S.: Coresets fork-means andk-medians and their applications. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), pp. 291–300 (2004)

    Google Scholar 

39. Har-Peled, S., Kushal, A.: Smaller coresets fork-median andk-means clustering. Discrete & Computational Geometry 37(1), 3–19 (2007)

    Article MathSciNet MATH  Google Scholar 

40. Indyk, P.: Sublinear time algorithms for metric space problems. In: Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC), pp. 428–434 (1999)

    Google Scholar 

41. Indyk, P.: A sublinear time approximation scheme for clustering in metric spaces. In: Proceedings of the 40th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 154–159 (1999)

    Google Scholar 

42. Indyk, P.: High-Dimensional Computational Geometry. PhD thesis, Stanford University (2000)

    Google Scholar 

43. Kumar, R., Rubinfeld, R.: Sublinear time algorithms. SIGACT News 34, 57–67 (2003)

    Article  Google Scholar 

44. Kumar, A., Sabharwal, Y., Sen, S.: A simple linear time (1 + ε)-approximation algorithm fork-means clustering in any dimensions. In: Proceedings of the 45th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 454–462 (2004)

    Google Scholar 

45. Kumar, A., Sabharwal, Y., Sen, S.: Linear time algorithms for clustering problems in any dimensions. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 1374–1385. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

46. Lovász, L., Szegedy, B.: Graph limits and testing hereditary graph properties. Technical Report, MSR-TR-2005-110, Microsoft Research (August 2005)

    Google Scholar 

47. Mettu, R., Plaxton, G.: Optimal time bounds for approximate clustering. Machine Learning 56(1-3), 35–60 (2004)

    Article MATH  Google Scholar 

48. Meyerson, A., O’Callaghan, L., Plotkin, S.: Ak-median algorithm with running time independent of data size. Machine Learning 56(1-3), 61–87 (2004)

    Article MATH  Google Scholar 

49. Mishra, N., Oblinger, D., Pitt, L.: Sublinear time approximate clustering. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 439–447 (2001)

    Google Scholar 

50. Muthukrishnan, S.: Data streams: Algorithms and applications. Foundations and Trends in Theoretical Computer Science 1(2) (August 2005)

    Google Scholar 

51. Nguyen, H., Onak, K.: Constant-time approximation algorithms via local improvements. In: Proceedings of the 49th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 489–498 (2008)

    Google Scholar 

52. Parnas, M., Ron, D., Rubinfeld, R.: Tolerant property testing and distance approximation. Journal of Computer and System Sciences 72(6), 1012–1042 (2006)

    Article MathSciNet MATH  Google Scholar 

53. Ron, D.: Property testing. In: Pardalos, P.M., Rajasekaran, S., Reif, J., Rolim, J.D.P. (eds.) Handobook of Randomized Algorithms, vol. II, pp. 597–649. Kluwer Academic Publishers, Dordrecht (2001)

    Chapter  Google Scholar 

54. Thorup, M.: Quickk-median,k-center, and facility location for sparse graphs. SIAM Journal on Computing 34(2), 405–432 (2005)

    Article MathSciNet MATH  Google Scholar 

55. Vazirani, V.V.: Approximation Algorithms. Springer, New York (2004)

    Google Scholar 

56. Yoshida, Y., Yamamoto, M., Ito, H.: Improved constant-time approximation algorithms for maximum independent sets and maximum matchings. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), pp. 225–234 (2009)

    Google Scholar 

Download references