Research output

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

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

Research output per year

Research output per year

Search results

• 2023

  On the geometric priority set cover problem

  Banik, A., Raman, R. & Ray, S., Jun 2023, In: Computational Geometry: Theory and Applications. 112, 101984.

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

  • Set Cover 100%
  • Approximation algorithms 85%
  • Sampling 55%
  • Unit Disk 41%
  • Set Systems 39%
• 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%

• On the Geometric Set Multicover Problem

  Raman, R. & Ray, S., Sep 2022, In: Discrete and Computational Geometry. 68, 2, p. 566-591 26 p.

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

  • Set Systems 100%
  • Set of points 73%
  • Hitting Set 54%
  • Demand 39%
  • Rectangle 38%
• 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

  Constructing Planar Support for Non-Piercing Regions

  Raman, R. & Ray, S., Oct 1 2020, In: Discrete and Computational Geometry. 64, 3, p. 1098-1122 25 p.

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

  • Hypergraph 100%
  • Covering Problem 49%
  • Packing Problem 48%
  • Colouring 35%
  • Intersection 30%

• 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%
• 2019

  A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs

  Elbassioni, K., Rauf, I. & Ray, S., May 3 2019, In: Theoretical Computer Science. 767, p. 26-33 8 p.

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

  Open Access

  • Parallel Algorithms 100%
  • Hitting Set 97%
  • Minimal Set 96%
  • Hypergraph 86%
  • Parallel algorithms 84%

• On a Problem of Danzer

  Mustafa, N. H. & Ray, S., May 1 2019, In: Combinatorics Probability and Computing. 28, 3, p. 473-482 10 p.

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

  • Polynomials 100%
  • Convex Hull 83%
  • Ball 69%
  • Disjoint 68%
  • Partition 64%
• 2018

  Corrigendum to “Faster algorithms for computing Hong's bound on absolute positiveness” [J. Symb. Comput. 45 (2010) 677–683] (S0747717110000301) (10.1016/j.jsc.2010.02.002))

  Koprowski, P., Mehlhorn, K. & Ray, S., Jul 1 2018, In: Journal of Symbolic Computation. 87, p. 238-241 4 p.

  Research output: Contribution to journal › Comment/debate › peer-review

  Open Access

  • Fast Algorithm 100%
  • Computing 62%
  • Linear-time Algorithm 52%
  • Univariate 43%
  • Roots 38%

• 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%

• Packing and Covering with Non-Piercing Regions

  Basu Roy, A., Govindarajan, S., Raman, R. & Ray, S., Sep 1 2018, In: Discrete and Computational Geometry. 60, 2, p. 471-492 22 p.

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

  • Packing 100%
  • Covering 83%
  • Packing Problem 20%
  • Set of points 15%
  • Cardinality 13%

• 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%

• Practical and efficient algorithms for the geometric hitting set problem

  Bus, N., Mustafa, N. H. & Ray, S., May 11 2018, In: Discrete Applied Mathematics. 240, p. 25-32 8 p.

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

  Open Access

  • Hitting Set 100%
  • Efficient Algorithms 62%
  • Set theory 46%
  • Data structures 30%
  • Data Structures 29%
• 2017

  Limits of Local Search: Quality and Efficiency

  Bus, N., Garg, S., Mustafa, N. H. & Ray, S., Apr 1 2017, In: Discrete and Computational Geometry. 57, 3, p. 607-624 18 p.

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

  • Local Search 100%
  • Polynomial Time Approximation Scheme 34%
  • Approximation 25%
  • Local Search Algorithm 19%
  • Hitting Set 19%

• ε -Mnets: Hitting Geometric Set Systems with Subsets

  Mustafa, N. H. & Ray, S., Apr 1 2017, In: Discrete and Computational Geometry. 57, 3, p. 625-640 16 p.

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

  • Set Systems 100%
  • Discrete Geometry 53%
  • Convex Geometry 52%
  • Optimal Bound 48%
  • Computational Geometry 46%
• 2016

  An optimal generalization of the Colorful Carathéodory theorem

  Mustafa, N. H. & Ray, S., Apr 6 2016, In: Discrete Mathematics. 339, 4, p. 1300-1305 6 p.

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

  Open Access

  • Set of points 100%
  • Generalization 73%
  • Hyperplane 69%
  • Theorem 58%
  • Point Sets 35%

• 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%

• Point line cover: The easy kernel is essentially tight

  Kratsch, S., Philip, G. & Ray, S., Apr 2016, In: ACM Transactions on Algorithms. 12, 3, 40.

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

  • Cover 100%
  • kernel 92%
  • Line 90%
  • Lower bound 89%
  • Communication Protocol 43%

• Tighter estimates for ∈-nets for disks

  Bus, N., Garg, S., Mustafa, N. H. & Ray, S., Feb 2016, In: Computational Geometry: Theory and Applications. 53, p. 27-35 9 p.

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

  Open Access

  • Hitting Set 100%
  • Set theory 62%
  • Approximation algorithms 52%
  • Estimate 44%
  • Approximation Algorithms 42%
• 2015

  Counting triangulations and other crossing-free structures approximately

  Alvarez, V., Bringmann, K., Ray, S. & Seidel, R., 2015, In: Computational Geometry: Theory and Applications. 48, 5, p. 386-397 12 p.

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

  Open Access

  • Triangulation 100%
  • Counting 77%
  • Exponential time 36%
  • Count 19%
  • Approximation 17%

• Counting Triangulations and Other Crossing-Free Structures via Onion Layers

  Alvarez, V., Bringmann, K., Curticapean, R. & Ray, S., Jun 1 2015, In: Discrete and Computational Geometry. 53, 4, p. 675-690 16 p.

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

  • Onion 100%
  • Triangulation 57%
  • Counting 51%
  • Cycle 10%
  • Computing 9%

• 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%

• K-Centerpoints Conjectures for Pointsets in R^d

  Mustafa, N. H., Ray, S. & Shabbir, M., Sep 1 2015, In: International Journal of Computational Geometry and Applications. 25, 3, p. 163-185 23 p.

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

  • Point Sets 100%
  • Ray Shooting 82%
  • Equivalence 35%
  • Generalise 27%
  • Theorem 20%

• Quasi-polynomial time approxim ation scheme for weighted geometric set cover on pseudodisks and halfspaces

  Mustafa, N. H., Raman, R. & Ray, S., 2015, In: SIAM Journal on Computing. 44, 6, p. 1650-1669 20 p.

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

  • Set Cover 100%
  • Half-space 74%
  • Polynomial time 63%
  • Polynomials 61%
  • Polynomial Time Approximation Scheme 58%
• 2014

  A separator theorem for intersecting objects in the plane

  Mustafa, N. H., Raman, R. & Ray, S., 2014, p. 380-385. 6 p.

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

  • Separator 100%
  • Object 56%
  • Geometric object 50%
  • Theorem 33%
  • Design of Algorithms 31%

• 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%

• On totally positive matrices and geometric incidences

  Farber, M., Ray, S. & Smorodinsky, S., Nov 2014, In: Journal of Combinatorial Theory. Series A. 128, 1, p. 149-161 13 p.

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

  Open Access

  • Totally Positive Matrices 100%
  • Incidence 64%
  • Minor 62%
  • Additive Combinatorics 24%
  • Combinatorial Geometry 22%

• 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%
• 2013

  Counting triangulations approximately

  Alvarez, V., Bringmann, K., Ray, S. & Seidel, R., 2013, p. 85-89. 5 p.

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

  • Triangulation 100%
  • Counting 90%
  • Exponential time 37%
  • Count 20%
  • Approximation 17%
• 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%

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

  Ajwani, D., Elbassioni, K., Govindarajan, S. & Ray, S., Jul 2012, In: Discrete and Computational Geometry. 48, 1, p. 39-52 14 p.

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

  Open Access

  • Conflict 100%
  • Rectangle 87%
  • Colouring 77%
  • Color 74%
  • Range of data 55%

• 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%

• On the complexity of the highway problem

  Elbassioni, K., Raman, R., Ray, S. & Sitters, R., Nov 16 2012, In: Theoretical Computer Science. 460, p. 70-77 8 p.

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

  Open Access

  • Profitability 100%
  • Path 77%
  • NP-hard 54%
  • Sales 54%
  • Polynomials 43%
• 2011

  Enumerating minimal transversals of geometric hypergraphs

  Elbassioni, K., Rauf, I. & Ray, S., 2011.

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

  • Hitting Set 100%
  • Minimal Set 99%
  • Hypergraph 88%
  • Geometric object 44%
  • Incremental Algorithm 26%

• 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

  Centerpoints and tverberg's technique

  Basit, A., Mustafa, N. H., Ray, S. & Raza, S., Aug 2010, In: Computational Geometry: Theory and Applications. 43, 6-7, p. 593-600 8 p.

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

  Open Access

  • Half-space 100%
  • Theorem 64%
  • Ball 42%
  • Trivial 42%
  • Upper bound 34%

• Faster algorithms for computing Hong's bound on absolute positiveness

  Mehlhorn, K. & Ray, S., Jun 2010, In: Journal of Symbolic Computation. 45, 6, p. 677-683 7 p.

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

  Open Access

  • Fast Algorithm 100%
  • Computing 62%
  • Isolation 60%
  • Real Roots 59%
  • Linear-time Algorithm 52%

• Hitting Simplices with Points in ℝ³

  Basit, A., Mustafa, N. H., Ray, S. & Raza, S., 2010, In: Discrete and Computational Geometry. 44, 3, p. 637-644 8 p.

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

  Open Access

  • Lemma 100%
  • Triangle 53%
  • Covering 50%
  • Open Problems 49%
  • Three-dimensional 44%

• Improved results on geometric hitting set problems

  Mustafa, N. H. & Ray, S., 2010, In: Discrete and Computational Geometry. 44, 4, p. 883-895 13 p.

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

  Open Access

  • Hitting Set 100%
  • Geometric object 88%
  • Local Search Algorithm 25%
  • Admissible Set 24%
  • Hits 21%

• 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%

• Reprint of: Weak ε-nets have basis of size

  Mustafa, N. H. & Ray, S., Aug 2010, In: Computational Geometry: Theory and Applications. 43, 6-7, p. 565-571 7 p.

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

  Open Access

  • Exponent 100%
  • Subset 71%
• 2009

  An optimal extension of the centerpoint theorem

  Mustafa, N. H. & Ray, S., Aug 2009, In: Computational Geometry: Theory and Applications. 42, 6-7, p. 505-510 6 p.

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

  • Theorem 100%
  • Convex Sets 90%
  • Hitting Set 67%
  • Hits 57%

• 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

  Matching edges and faces in polygonal partitions

  Aichholzer, O., Aurenhammer, F., Gonzalez-Nava, P., Hackl, T., Huemer, C., Hurtado, F., Krasser, H., Ray, S. & Vogtenhuber, B., Feb 2008, In: Computational Geometry: Theory and Applications. 39, 2, p. 134-141 8 p.

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

  Open Access

  • Pseudo-triangulation 100%
  • Triangulation 70%
  • Partition 46%
  • Quadrangulation 44%
  • Tree Decomposition 41%

• 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%

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

  Mustafa, N. H. & Ray, S., May 2008, In: Computational Geometry: Theory and Applications. 40, 1, p. 84-91 8 p.

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

  Open Access

  • Exponent 100%
  • Subset 71%