Find Research outputs

Search results

• Approximation algorithms for Polynomial-Expansion and Low-Density graphs

  Har-Peled, S. & Quanrud, K., 2015, Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings. Bansal, N. & Finocchi, I. (eds.). Springer, p. 717-728 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 9294).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

• Approximation algorithms for polynomial-expansion and low-density graphs

  Har-Peled, S. & Quanrud, K., 2017, In: SIAM Journal on Computing. 46, 6, p. 1712-1744 33 p.

  Research output: Contribution to journal › Article › peer-review

• Approximation algorithms for non-uniform buy-at-bulk network design

  Chekuri, C., Hajiaghayi, M. T., Kortsarz, G. & Salavatipour, M. R., 2006, 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006. p. 677-686 10 p. 4031402. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

• Approximation algorithms for nonuniform buy-at-bulk network design

  Chekuri, C., Hajiaghayi, M. T., Kortsarz, G. & Salavatipour, M. R., 2010, In: SIAM Journal on Computing. 39, 5, p. 1772-1798 27 p.

  Research output: Contribution to journal › Article › peer-review

• Approximation algorithms for node-weighted buy-at-bulk network design

  Chekuri, C., Hajiaghayi, M. T., Kortsarz, G. & Salavatipour, M. R., 2007, Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007. Association for Computing Machinery, p. 1265-1274 10 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 07-09-January-2007).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

• Approximation Algorithms for Minimum-Width Annuli and Shells

  Agarwal, P. K., Aronov, B., Har-Peled, S. & Sharir, M., Dec 2000, In: Discrete and Computational Geometry. 24, 4, p. 687-705 19 p.

  Research output: Contribution to journal › Article › peer-review

  Open Access

• Approximation algorithms for minimizing average weighted completion time

  Chekuri, C. & Khanna, S., Jan 1 2004, Handbook of Scheduling: Algorithms, Models, and Performance Analysis. CRC Press, p. 11-1-11-30

  Research output: Chapter in Book/Report/Conference proceeding › Chapter

• Approximation Algorithms for Maximum Matchings in Geometric Intersection Graphs

  Har-Peled, S. & Yang, E., Jun 1 2022, 38th International Symposium on Computational Geometry, SoCG 2022. Goaoc, X. & Kerber, M. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 47. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 224).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

• Approximation Algorithms for Maximum Independent Set of Pseudo-Disks

  Chan, T. M. & Har-Peled, S., Sep 2012, In: Discrete and Computational Geometry. 48, 2, p. 373-392 20 p.

  Research output: Contribution to journal › Article › peer-review

• Approximation algorithms for maximum independent set of pseudo-disks

  Chan, T. M. & Har-Peled, S., 2009, Proceedings of the 25th Annual Symposium on Computational Geometry, SCG'09. p. 333-340 8 p. (Proceedings of the Annual Symposium on Computational Geometry).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

• Approximation algorithms for maximum cliques in 3D unit-disk graphs

  Afshani, P. & Chan, T. M., 2005, p. 19-22. 4 p.

  Research output: Contribution to conference › Paper › peer-review

• Approximation algorithms for Euler genus and related problems

  Chekuri, C. & Sidiropoulos, A., 2013, Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013. p. 167-176 10 p. 6686152. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

• Approximation algorithms for euler genus and related problems

  Chekuri, C. & Sidiropoulos, A., 2018, In: SIAM Journal on Computing. 47, 4, p. 1610-1643 34 p.

  Research output: Contribution to journal › Article › peer-review

• Approximation Algorithms for Directed Steiner Problems

  Charikar, M., Chekuri, C., Cheung, T. Y., Dai, Z., Goel, A., Guha, S. & Li, M., Oct 1999, In: Journal of Algorithms. 33, 1, p. 73-91 19 p.

  Research output: Contribution to journal › Article › peer-review

• Approximation algorithms for directed Steiner problems

  Charikar, M., Chekuri, C., Cheung, T. Y., Dai, Z., Goel, A., Guha, S. & Li, M., 1998, p. 192-200. 9 p.

  Research output: Contribution to conference › Paper › peer-review

• Approximation algorithms and hardness of the k-route cut problem

  Chuzhoy, J., Makarychev, Y., Vijayaraghavan, A. & Zhou, Y., Dec 1 2015, In: ACM Transactions on Algorithms. 12, 1, 2.

  Research output: Contribution to journal › Article › peer-review

  Open Access

• Approximation algorithms and hardness of the k-route cut problem

  Chuzhoy, J., Makarychev, Y., Vijayaraghavan, A. & Zhou, Y., Apr 30 2012, Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012. Association for Computing Machinery, p. 780-799 20 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

• Approximating warps with intra-warp operand value similarity

  Wong, D., Kim, N. S. & Annavaram, M., Apr 1 2016, Proceedings of the 2016 IEEE International Symposium on High-Performance Computer Architecture, HPCA 2016. IEEE Computer Society, p. 176-187 12 p. 7446063. (Proceedings - International Symposium on High-Performance Computer Architecture; vol. 2016-April).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

• Approximating the Transition Probability Function Corresponding to the Solution of Stochastic Optimal Velocity Dynamical Model

  Matin, H. N. Z. & Sowers, R. B., May 25 2021, 2021 American Control Conference, ACC 2021. Institute of Electrical and Electronics Engineers Inc., p. 3326-3332 7 p. 9483012. (Proceedings of the American Control Conference; vol. 2021-May).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

• Approximating the smallest grammar: Kolmogorov complexity in natural models

  Charikar, M., Lehman, E., Liu, D., Panigrahy, R., Prabhakaran, M., Rasala, A., Sahai, A. & Shelat, A., 2002, In: Conference Proceedings of the Annual ACM Symposium on Theory of Computing. p. 792-801 10 p.

  Research output: Contribution to journal › Conference article › peer-review

• Approximating the piercing number for unit-height rectangles

  Chan, T. M. & Mahmood, A. A., 2005, p. 15-18. 4 p.

  Research output: Contribution to conference › Paper › peer-review

• Approximating the Nash social welfare with budget-additive valuations

  Garg, J., Hoefer, M. & Mehlhorn, K., 2018, 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. Czumaj, A. (ed.). Association for Computing Machinery, p. 2326-2340 15 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

• Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points

  Chan, T. M. & Rahmati, Z., Jan 1 2017, In: Computational Geometry: Theory and Applications. 60, p. 2-7 6 p.

  Research output: Contribution to journal › Article › peer-review

  Open Access

• Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points

  Chan, T. M. & Rahmati, Z., 2015, p. 136-140. 5 p.

  Research output: Contribution to conference › Paper › peer-review

• Approximating the metastable defect concentration in supersaturated materials: A case study of the SrTiO ₃/TiO ₂system

  Sun, L., Mao, S. & Dillon, S. J., Feb 2012, In: Journal of the American Ceramic Society. 95, 2, p. 788-792 5 p.

  Research output: Contribution to journal › Article › peer-review

• Approximating the Maximum Overlap of Polygons under Translation

  Har-Peled, S. & Roy, S., May 1 2017, In: Algorithmica. 78, 1, p. 147-165 19 p.

  Research output: Contribution to journal › Article › peer-review

• Approximating the maximum overlap of polygons under translation

  Har-Peled, S. & Roy, S., 2014, Algorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings. Springer, p. 542-553 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8737 LNCS).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

• Approximating the k-level in three-dimensional plane arrangements

  Har-Peled, S., Kaplan, H. & Sharir, M., Jan 1 2017, A Journey through Discrete Mathematics: A Tribute to Jiri Matousek. Springer, p. 467-503 37 p.

  Research output: Chapter in Book/Report/Conference proceeding › Chapter

• Approximating the Ideal Observer for Joint Signal Detection and Localization Tasks by use of Supervised Learning Methods

  Zhou, W., Li, H. & Anastasio, M. A., Dec 2020, In: IEEE transactions on medical imaging. 39, 12, p. 3992-4000 9 p., 9139307.

  Research output: Contribution to journal › Article › peer-review

  Open Access

• Approximating the Ideal Observer and Hotelling Observer for Binary Signal Detection Tasks by Use of Supervised Learning Methods

  Zhou, W., Li, H. & Anastasio, M. A., Oct 2019, In: IEEE transactions on medical imaging. 38, 10, p. 2456-2468 13 p., 8691467.

  Research output: Contribution to journal › Article › peer-review

  Open Access

• Approximating the held-karp bound for metric TSP in nearly-linear time

  Chekuri, C. & Quanrud, K., Nov 10 2017, Proceedings - 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017. IEEE Computer Society, p. 789-800 12 p. 8104110. (Annual Symposium on Foundations of Computer Science - Proceedings; vol. 2017-October).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

• Approximating the Fréchet distance for realistic curves in near linear time

  Driemel, A., Har-Peled, S. & Wenk, C., 2010, Proceedings of the 26th Annual Symposium on Computational Geometry, SCG'10. p. 365-374 10 p. (Proceedings of the Annual Symposium on Computational Geometry).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

• Approximating the Fréchet distance for realistic curves in near linear time

  Driemel, A., Har-Peled, S. & Wenk, C., Jul 2012, In: Discrete and Computational Geometry. 48, 1, p. 94-127 34 p.

  Research output: Contribution to journal › Article › peer-review

• Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus

  Chan, T. M., 2000, p. 300-309. 10 p.

  Research output: Contribution to conference › Paper › peer-review

• Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus

  Chan, T. M., 2002, In: International Journal of Computational Geometry and Applications. 12, 1-2, p. 67-85 19 p.

  Research output: Contribution to journal › Article › peer-review

• Approximating the complement of the maximum compatible subset of leaves of k trees

  Ganapathy, G. & Warnow, T., 2002, Approximation Algorithms for Combinatorial Optimization - 5th International Workshop, APPROX 2002, Proceedings. Jansen, K., Leonardi, S. & Vazirani, V. (eds.). Springer, p. 122-134 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 2462).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

• Approximating the a;-level in three-dimensional plane arrangements

  Har-Peled, S., Kaplan, H. & Sharir, M., 2016, 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016. Krauthgamer, R. (ed.). Association for Computing Machinery, p. 1193-1212 20 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

• Approximating text-to-pattern Hamming distances

  Chan, T. M., Golan, S., Kociumaka, T., Kopelowitz, T. & Porat, E., Jun 8 2020, STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G. & Chuzhoy, J. (eds.). Association for Computing Machinery, p. 643-656 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

  Open Access

• Approximating Steiner k-cuts

  Chekuri, C., Guha, S. & Naor, J., 2003, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Baeten, J. C. M., Lenstra, J. K., Parrow, J. & Woeginger, G. J. (eds.). Springer, p. 189-199 11 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 2719).

  Research output: Chapter in Book/Report/Conference proceeding › Chapter

• Approximating shortest paths on a convex polytope in three dimensions

  Agarwal, P. K., Har-Peled, S., Sharir, M. & Varadarajan, K. R., Jul 1997, In: Journal of the ACM. 44, 4, p. 567-584 18 p.

  Research output: Contribution to journal › Article › peer-review

• Approximating shortest paths on a convex polytope in three dimensions

  Har-Peled, S., Sharir, M. & Varadarajan, K. R., 1996, p. 329-338. 10 p.

  Research output: Contribution to conference › Paper › peer-review

  Open Access

• Approximating sensitivity of failure probability in reliability-based design optimization

  Liu, K., Paulino, G. H. & Gardoni, P., 2015, 12th International Conference on Applications of Statistics and Probability in Civil Engineering, ICASP 2015. University of British Columbia, (12th International Conference on Applications of Statistics and Probability in Civil Engineering, ICASP 2015).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

• Approximating probabilistic automata by regular languages

  Chadha, R., Sistla, A. P. & Viswanathan, M., Aug 1 2018, Computer Science Logic 2018, CSL 2018. Ghica, D. R. & Jung, A. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 14. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 119).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

• Approximating Nash social welfare under submodular valuations through (un)matchings

  Garg, J., Kulkarni, P. & Kulkarni, R., 2020, 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020. Chawla, S. (ed.). Association for Computing Machinery, p. 2673-2687 15 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2020-January).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

• Approximating Nash social welfare under rado valuations

  Garg, J., Husić, E. & Végh, L. A., Jun 15 2021, STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. Khuller, S. & Williams, V. V. (eds.). Association for Computing Machinery, p. 1412-1425 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

• Approximating multicut and the demand graph

  Chekuri, C. & Madan, V., 2017, 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017. Klein, P. N. (ed.). Association for Computing Machinery, p. 855-874 20 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 0).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

  Open Access

• Approximating minimization diagrams and generalized proximity search

  Har-Peled, S. & Kumar, N., 2013, Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013. p. 717-726 10 p. 6686208. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

• Approximating minimization diagrams and generalized proximity search

  Har-Peled, S. & Kumar, N., 2015, In: SIAM Journal on Computing. 44, 4, p. 944-974 31 p.

  Research output: Contribution to journal › Article › peer-review

• Approximating maximin share allocations

  Garg, J., McGlaughlin, P. & Taki, S., Jan 2019, 2nd Symposium on Simplicity in Algorithms, SOSA 2019 - Co-located with the 30th ACM-SIAM Symposium on Discrete Algorithms, SODA 2019. Fineman, J. T. & Mitzenmacher, M. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, (OpenAccess Series in Informatics; vol. 69).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

• Approximating k-hop minimum-spanning trees

  Althaus, E., Funke, S., Har-Peled, S., Könemann, J., Ramos, E. A. & Skutella, M., Mar 2005, In: Operations Research Letters. 33, 2, p. 115-120 6 p.

  Research output: Contribution to journal › Article › peer-review