Research output

Research output per year 2005 2007 2008 2009 2010 2012 2014 2015 2016 2018 2020 2023

• 27 Article
• 23 Conference contribution
• 5 Paper
• 1 Comment/debate

Research output per year

Research output per year

Search results

• 2022

  Learning to Prune Instances of k-median and Related Problems

  Tayebi, D., Ray, S. & Ajwani, D., 2022, SIAM Symposium on Algorithm Engineering and Experiments, ALENEX 2022. Society for Industrial and Applied Mathematics Publications, p. 184-194 11 p. (Proceedings of the Workshop on Algorithm Engineering and Experiments; vol. 2022-January).

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

  • Approximation algorithms 100%
  • Learning 84%
  • Machine learning 67%
  • Combinatorial optimization 67%
  • Classifiers 65%
• 2021

  On Geometric Priority Set Cover Problems

  Banik, A., Raman, R. & Ray, S., Dec 1 2021, 32nd International Symposium on Algorithms and Computation, ISAAC 2021. Ahn, H-K. & Sadakane, K. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 12. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 212).

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

  • Approximation algorithms 100%
  • Sampling 64%
• 2020

  Improved approximation algorithm for set multicover with non-piercing regions

  Raman, R. & Ray, S., Aug 1 2020, 28th Annual European Symposium on Algorithms, ESA 2020. Grandoni, F., Herman, G. & Sanders, P. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 78. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 173).

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

  • Approximation algorithms 100%
  • Polynomials 71%
  • Set theory 59%
• 2018

  On a problem of danzer

  Mustafa, N. H. & Ray, S., Aug 1 2018, 26th European Symposium on Algorithms, ESA 2018. Bast, H., Herman, G. & Azar, Y. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, (Leibniz International Proceedings in Informatics, LIPIcs; vol. 112).

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

  • Polynomials 100%

• Planar support for non-piercing regions and applications

  Raman, R. & Ray, S., Aug 1 2018, 26th European Symposium on Algorithms, ESA 2018. Bast, H., Herman, G. & Azar, Y. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, (Leibniz International Proceedings in Informatics, LIPIcs; vol. 112).

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

  • Coloring 100%
  • Polynomials 32%
  • Visualization 32%
• 2016

  Packing and covering with non-piercing regions

  Govindarajan, S., Raman, R., Ray, S. & Roy, A. B., Aug 1 2016, 24th Annual European Symposium on Algorithms, ESA 2016. Zaroliagis, C. & Sankowski, P. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 47. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 57).

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

  • Polynomials 100%
  • Set theory 83%
  • Geometry 78%
• 2015

  Geometric hitting sets for disks: Theory and practice

  Bus, N., Mustafa, N. H. & Ray, S., 2015, Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings. Bansal, N. & Finocchi, I. (eds.). Springer Verlag, p. 903-914 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

  • Hitting Set 100%
  • Set theory 46%
  • Data Structures 29%
  • Geometric Optimization 21%
  • Combinatorial optimization 20%

• Improved local search for geometric hitting set

  Bus, N., Garg, S., Mustafa, N. H. & Ray, S., Feb 1 2015, 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015. Mayr, E. W. & Ollinger, N. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 184-196 13 p. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 30).

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

  • Polynomials 100%
  • Combinatorial optimization 47%
  • Approximation algorithms 46%
  • Set theory 27%
• 2014

  Near-optimal generalisations of a theorem of Macbeath

  Mustafa, N. H. & Ray, S., Mar 1 2014, 31st International Symposium on Theoretical Aspects of Computer Science, STACS 2014. Mayr, E. W. & Portier, N. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Vol. 25. p. 578-589 12 p.

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

  • Computational geometry 100%
  • Geometry 45%

• Point line cover: The easy kernel is essentially tight

  Kratsch, S., Philip, G. & Ray, S., 2014, Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014. Association for Computing Machinery, p. 1596-1606 11 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

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

  • Polynomials 100%
  • Cover 95%
  • kernel 88%
  • Line 86%
  • Network protocols 53%

• Settling the APX-hardness status for geometric set cover

  Mustafa, N. H., Raman, R. & Ray, S., Dec 7 2014, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. IEEE Computer Society, p. 541-550 10 p. 6979039. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

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

  • Separators 100%
  • Approximation algorithms 99%
  • NP-hard 89%
  • Hardness 72%
  • Sampling 64%
• 2012

  A theorem of bárány revisited and extended

  Mustafa, N. H. & Ray, S., 2012, Proceedings of the 28th Annual Symposuim on Computational Geometry, SCG 2012. p. 333-337 5 p. (Proceedings of the Annual Symposium on Computational Geometry).

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

  • Set of points 100%
  • Hyperplane 69%
  • Theorem 58%
  • Point Sets 35%
  • Convex Hull 35%

• Counting crossing-free structures

  Alvarez, V., Bringmann, K., Curticapean, R. & Ray, S., 2012, Proceedings of the 28th Annual Symposuim on Computational Geometry, SCG 2012. p. 61-68 8 p. (Proceedings of the Annual Symposium on Computational Geometry).

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

  • Triangulation 100%
  • Counting 90%
  • Onion 14%
  • Cycle 12%
  • Computing 10%
• 2011

  Ray-shooting depth: Computing statistical data depth of point sets in the plane

  Mustafa, N. H., Ray, S. & Shabbir, M., 2011, Algorithms, ESA 2011 - 19th Annual European Symposium, Proceedings. p. 506-517 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6942 LNCS).

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

  • Ray Shooting 100%
  • Data Depth 95%
  • Statistical Computing 88%
  • Approximation algorithms 66%
  • Set of points 56%
• 2010

  Improving the first selection lemma in ℝ³

  Basit, A., Mustafa, N. H., Ray, S. & Raza, S., 2010, Proceedings of the 26th Annual Symposium on Computational Geometry, SCG'10. p. 354-357 4 p. (Proceedings of the Annual Symposium on Computational Geometry).

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

  • Lemma 100%
  • Lower bound 82%
  • Upper and Lower Bounds 52%
  • Open Problems 49%
  • Three-dimensional 44%
• 2009

  On profit-maximizing pricing for the highway and tollbooth problems

  Elbassioni, K., Raman, R., Ray, S. & Sitters, R., 2009, Algorithmic Game Theory - Second International Symposium, SAGT 2009, Proceedings. p. 275-286 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5814 LNCS).

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

  • Profit 100%
  • Purchasing 99%
  • Pricing 95%
  • Profitability 77%
  • Customers 50%

• On the approximability of the maximum feasible subsystem problem with 0/1-coefficients

  Elbassioni, K., Raman, R., Ray, S. & Sitters, R., 2009, Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms. Association for Computing Machinery (ACM), p. 1210-1219 10 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

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

  • Approximability 100%
  • Subsystem 84%
  • Inapproximability 72%
  • Approximation algorithms 46%
  • Coefficient 43%

• PTAS for geometric hitting set problems via local search

  Mustafa, N. H. & Ray, S., 2009, Proceedings of the 25th Annual Symposium on Computational Geometry, SCG'09. p. 17-22 6 p. (Proceedings of the Annual Symposium on Computational Geometry).

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

  • Hitting Set 100%
  • Geometric object 88%
  • Local Search 86%
  • Local Search Algorithm 25%
  • Admissible Set 24%
• 2008

  New existence proofs for ε-nets

  Pyrga, E. & Ray, S., 2008, Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08. p. 199-207 9 p. (Proceedings of the Annual Symposium on Computational Geometry).

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

  • Hypergraph 100%
  • VC Dimension 46%
  • Dimension Theory 46%
  • Half-space 32%
  • Set of points 31%
• 2007

  An optimal generalization of the centerpoint theorem, and its extensions

  Mustafa, N. & Ray, S., 2007, Proceedings of the Twenty-third Annual Symposium on Computational Geometry, SCG'07. p. 138-141 4 p. (Proceedings of the Annual Symposium on Computational Geometry).

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

  • Generalization 100%
  • Theorem 79%
  • Hitting Set 54%
  • Hits 46%
  • Convex Sets 36%

• Conflict-free coloring for rectangle ranges using O(n^.382) colors

  Ajwani, D., Elbassioni, K., Govindarajan, S. & Ray, S., 2007, SPAA'07: Proceedings of the Nineteenth Annual Symposium on Parallelism in Algorithms and Architectures. p. 181-187 7 p. (Annual ACM Symposium on Parallelism in Algorithms and Architectures).

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

  • Coloring 100%
  • Color 60%
  • Base stations 18%
  • Polynomials 16%

• On computing the centroid of the vertices of an arrangement and related problems

  Ajwani, D., Ray, S., Seidel, R. & Tiwary, H. R., 2007, Algorithms and Data Structures - 10th International Workshop, WADS 2007, Proceedings. Springer Verlag, p. 519-528 10 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4619 LNCS).

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

  • Centroid 100%
  • Arrangement 81%
  • Computing 52%
  • Chord or secant line 30%
  • Enumeration 25%

• Weak -nets have basis of size o(1/ log (1/)) in any dimension

  Mustafa, N. & Ray, S., 2007, Proceedings of the Twenty-third Annual Symposium on Computational Geometry, SCG'07. p. 239-244 6 p. (Proceedings of the Annual Symposium on Computational Geometry).

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

  • Exponent 100%
  • Subset 71%