Draft:Arindam Khan



Arindam Khan is an Indian computer scientist who works as an Associate Professor at Indian Institute of Science[1]. His research concerns computational geometry, online algorithms, and approximation algorithms.

He studied in Uttarpara Govt. High School [2]. He graduated from IIT Kharagpur in 2009, earned a bachelor's and a master's degree in computer science and engineering. He completed his doctorate in 2015 at the Georgia Institute of Technology, Atlanta under the supervision of Prasad Tetali. His Erdős number is 2 via Prasad Tetali [3].

Arindam is renowned for his work on geometric approximation algorithms and has given improved approximation algorithms for many fundamental problems in multidimensional packing and covering, such as Knapsack problem [4], Strip packing problem [5], Guillotine cutting [6], Maximum disjoint set [7], etc. He is also an author of an influential survey on bin packing [8].

His breakthrough research on the maximum independent set of rectangles was mentioned as one of the top results in theory research in India in the Communications of the ACM (CACM) [9]. Another seminal result on bin packing, where he made progress on celebrated Kenyon's Best-Fit bin packing conjecture after three decades, was mentioned in SIGACT news [10], [11].

He is a recipient of the Best Paper Award in 45th International Symposium on Mathematical Foundations of Computer Science [12], prestigious Google India Research Award [13], and Prof. Priti Shankar Teaching Award [14]. He has served in the program committee of top-tier computer science conferences, including Symposium on Computational Geometry (SOCG) 2023 [15], ACM-SIAM Symposium on Discrete Algorithms (SODA) 2025 [16] and 2026 [17].

Arindam is also popular for science communication and one of the most followed computer scientists in the world on LinkedIn with more than 20,000 followers (and also thousands of followers on Twitter and Quora) [18].

  1. ^ https://www.csa.iisc.ac.in/~arindamkhan/ Homepage
  2. ^ Cascade, retrieved 2025-04-04.
  3. ^ Erdos Number, retrieved 2025-04-04.
  4. ^ Galvez, Waldo; Grandoni, Fabrizio; Ingala, Salvatore; Heydrich, Sandy; Khan, Arindam; Wiese, Andreas (2021). "Approximating Geometric Knapsack via L-packings". ACM Trans. Algorithms. 17 (4): 33:1–33:67. arXiv:1711.07710. doi:10.1145/3473713.
  5. ^ Gálvez, Waldo; Grandoni, Fabrizio; Ingala, Salvatore; Khan, Arindam (2016). Improved Pseudo-Polynomial-Time Approximation for Strip Packing. Leibniz International Proceedings in Informatics (LIPIcs). Vol. 65. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. pp. 9:1–9:14. doi:10.4230/LIPIcs.FSTTCS.2016.9. ISBN 9783959770279. S2CID 3205478.
  6. ^ Khan, Arindam; Pittu, Madhusudhan Reddy (2020). Byrka, Jaros\law; Meka, Raghu (eds.). "On Guillotine Separability of Squares and Rectangles". Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs). 176. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum für Informatik: 47:1–47:22. doi:10.4230/LIPIcs.APPROX/RANDOM.2020.47. ISBN 978-3-95977-164-1.
  7. ^ Gálvez, Waldo; Khan, Arindam; Mari, Mathieu; Mömke, Tobias; Pittu, Madhusudhan Reddy; Wiese, Andreas (2022-01-01), "A 3-Approximation Algorithm for Maximum Independent Set of Rectangles", Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Proceedings, Society for Industrial and Applied Mathematics, pp. 894–905, doi:10.1137/1.9781611977073.38, ISBN 978-1-61197-707-3, S2CID 235265867, retrieved 2022-09-29
  8. ^ Christensen, Henrik; Khan, Arindam; Pokutta, Sebastian; Tetali, Prasad (2017). Approximation and online algorithms for multidimensional bin packing: A survey. Computer Science Review. Vol. 24. ScienceDirect. pp. 63–79. doi:10.1016/J.COSREV.2016.12.001.
  9. ^ Theory Research in India, retrieved 2025-04-04.
  10. ^ SIGACT News: 2022 in review, retrieved 2025-04-04.
  11. ^ SIGACT News: 2024 in review, retrieved 2025-04-04.
  12. ^ MFCS Best Paper, retrieved 2025-04-04.
  13. ^ Google India Research Award, retrieved 2025-04-04.
  14. ^ PritiShankarAward, retrieved 2025-04-04.
  15. ^ SOCG 2023, retrieved 2025-04-04.
  16. ^ SODA 2025, retrieved 2025-04-04.
  17. ^ SODA 2026, retrieved 2025-04-04.
  18. ^ LinkedIn Profile, retrieved 2025-04-04.

© MMXXIII Rich X Search. We shall prevail. All rights reserved. Rich X Search