Browse by Fellow

Gupta, Anupam ; Kumar, Amit ; Panigrahi, Debmalya (2020) Caching with time windows In: STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, June 22 - 26, 2020, Chicago IL USA.

Goyal, Dishant ; Jaiswal, Ragesh ; Kumar, Amit (2020) FPT Approximation for Constrained Metric k-Median/Means In: 15th International Symposium on Parameterized and Exact Computation (IPEC 2020).

Jaiswal, Ragesh ; Kumar, Amit (2020) Multiplicative Rank-1 Approximation using Length-Squared Sampling In: Symposium on Simplicity in Algorithms (SOSA), 2020.

Bhattacharya, Anup ; Goyal, Dishant ; Jaiswal, Ragesh ; Kumar, Amit (2020) On Sampling Based Algorithms for k-Means In: 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020).

Gupta, Anupam ; Krishnaswamy, Ravishankar ; Kumar, Amit ; Singla, Sahil (2020) Online Carpooling using Expander Decompositions In: 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020).

Gupta, Anupam ; Kumar, Amit ; Nagarajan, Viswanath ; Shen, Xiangkun (2020) Stochastic Makespan Minimization in Structured Set Systems In: Integer Programming and Combinatorial Optimization, June 8–10, 2020, London, UK.

Garg, Naveen ; Gupta, Anupam ; Kumar, Amit ; Singla, Sahil (2019) Non-clairvoyant precedence constrained scheduling In: 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, Jul 9 2019 → Jul 12 2019, Patras, Greece.

Gupta, Anupam ; Krishnaswamy, Ravishankar ; Kumar, Amit ; Panigrahi, Debmalya (2019) Elastic Caching In: Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Jan 6-9, 2019, California, USA.

Gupta, Anupam ; Kumar, Amit ; Nagarajan, Viswanath ; Shen, Xiangkun (2019) Stochastic Load Balancing on Unrelated Machines In: ACM-SIAM Symposium on Discrete Algorithms (SODA).

Cohen-Addad, Vincent ; Gupta, Anupam ; Kumar, Amit ; Lee, Euiwoong ; Li, Jason (2019) Tight FPT Approximations for k-Median and k-Means In: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), 8-12 July 2019, Patras, Greece.

Ailon, Nir ; Bhattacharya, Anup ; Jaiswal, Ragesh ; Kumar, Amit (2018) Approximate Clustering with Same-Cluster Queries In: 9th Innovations in Theoretical Computer Science Conference (ITCS 2018).

Adamaszek, Anna ; Antoniadis, Antonios ; Kumar, Amit ; Mömke, Tobias (2018) Approximating Airports and Railways In: 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018).

Batra, Jatin ; Garg, Naveen ; Kumar, Amit (2018) Constant Factor Approximation Algorithm for Weighted Flow Time on a Single Machine in Pseudo-polynomial time In: 59th Annual Symposium on Foundations of Computer Science, October 7-9, 2018, Paris, France.

Bhattacharya, Anup ; Jaiswal, Ragesh ; Kumar, Amit (2018) Faster Algorithms for the Constrained k-means Problem Theory of Computing Systems, 62 (1). pp. 93-115. ISSN 1432-4350

Gupta, Anupam ; Guruganesh, Guru ; Kumar, Amit ; Wajc, David (2018) Fully-Dynamic Bin Packing with Limited Repacking In: International Colloquium on Automata, Languages and Programming (ICALP), July 9-13, 2018, Prague, Czech Republic.

Groß, Martin ; Gupta, Anupam ; Kumar, Amit ; Matuschke, Jannik ; Schmidt, Daniel R. ; Schmidt, Melanie ; Verschae, José (2018) A Local-Search Algorithm for Steiner Forest In: Innovations in Theoretical Computer Science (ITCS), January 11-14, 2018, Massachusetts, USA.

Gupta, Anupam ; Kumar, Amit ; Li, Jason (2018) Non-Preemptive Flow-Time Minimization via Rejections In: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018).

Choudhury, Anamitra Roy ; Das, Syamantak ; Garg, Naveen ; Kumar, Amit (2018) Rejecting jobs to minimize load and maximum flow-time Journal of Computer and System Sciences, 91 . pp. 42-68. ISSN 0022-0000

Chakrabarty, Deeparnab ; Krishnaswamy, Ravishankar ; Kumar, Amit (2017) The Heterogeneous Capacitated k-Center Problem Lecture Notes in Computer Science, 10328 . pp. 123-135. ISSN 0302-9743

Gupta, Anupam ; Krishnaswamy, Ravishankar ; Kumar, Amit ; Panigrahi, Debmalya (2017) Online and dynamic algorithms for set cover In: STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, June 19 - 23, 2017, Montreal, Canada.

Gupta, Anupam ; Kumar, Amit (2015) Greedy Algorithms for Steiner Forest In: STOC '15: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, June 14 - 17, 2015, Portland, Oregon USA.

Choudhury, Anamitra Roy ; Das, Syamantak ; Kumar, Amit (2015) Minimizing Weighted lp-Norm of Flow-Time in the Rejection Model In: 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015).

Batra, Jatin ; Garg, Naveen ; Kumar, Amit ; Mömke, Tobias ; Wiese, Andreas (2015) New Approximation Schemes for Unsplittable Flow on a Path In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, January 4 - 6, 2015, San Diego, California.

Bhattacharya, Anup ; Issac, Davis ; Jaiswal, Ragesh ; Kumar, Amit (2015) Sampling in Space Restricted Settings Lecture Notes in Computer Science, 9198 . pp. 483-494. ISSN 0302-9743

Bera, Suman Kalyan ; Das, Syamantak ; Kumar, Amit (2014) Minimizing Average Flow-Time under Knapsack Constraint Lecture Notes in Computer Science, 8591 . pp. 584-595. ISSN 0302-9743

Kumar, Amit (2013) Constant Factor Approximation Algorithm for the Knapsack Median Problem In: Proceedings of the 2012 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).

Gupta, Anupam ; Kumar, Amit ; Stein, Cliff (2013) Maintaining Assignments Online: Matching, Scheduling, and Flows In: Proceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).

Krishnaswamy, Ravishankar ; Kumar, Amit ; Nagarajan, Viswanath ; Sabharwal, Yogish ; Saha, Barna (2013) The Matroid Median Problem In: Proceedings of the 2011 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).

Anand, S. ; Bringmann, Karl ; Friedrich, Tobias ; Garg, Naveen ; Kumar, Amit (2013) Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines Lecture Notes in Computer Science, 7965 . pp. 13-24. ISSN 0302-9743

Kumar, Amit ; Manokaran, Rajsekar ; Tulsiani, Madhur ; Vishnoi, Nisheeth K. (2013) On LP-based Approximability for Strict CSPs In: Proceedings of the 2011 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).

Gupta, Anupam ; Kumar, Amit (2013) Online Steiner Tree with Deletions In: ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014.

Anand, S. ; Garg, Naveen ; Kumar, Amit (2013) Resource Augmentation for Weighted Flow-time explained by Dual Fitting In: Proceedings of the 2012 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).

Elbassioni, Khaled ; Garg, Naveen ; Gupta, Divya ; Kumar, Amit ; Narula, Vishal ; Pal, Arindam (2012) Approximation Algorithms for the Unsplittable Flow Problem on Paths and Trees In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012).

Kumar, Amit ; Panda, Preeti Ranjan ; Sarangi, Smruti R. (2012) Efficient on-line algorithm for maintaining k-cover of sparse bit-strings In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2012, December 15-17, 2012, Hyderabad, India.

Jaiswal, Ragesh ; Kumar, Amit ; Sen, Sandeep (2012) A Simple D 2-Sampling Based PTAS for k-Means and other Clustering Problems Lecture Notes in Computer Science, 7434 . pp. 13-24. ISSN 0302-9743

Dhesi, Aman ; Gupta, Pranav ; Kumar, Amit ; Parija, Gyana R. ; Roy, Sambuddha (2011) Contact Center Scheduling with Strict Resource Requirements Lecture Notes in Computer Science, 6655 . pp. 156-169. ISSN 0302-9743

Chakaravarthy, Venkatesan T. ; Kumar, Amit ; Roy, Sambuddha ; Sabharwal, Yogish (2011) Resource Allocation for Covering Time Varying Demands Lecture Notes in Computer Science, 6942 . pp. 543-554. ISSN 0302-9743

Chakaravarthy, Venkatesan T. ; Kumar, Amit ; Pandit, Vinayaka ; Roy, Sambuddha ; Sabharwal, Yogish (2011) Scheduling Resources for Throughput Maximization Lecture Notes in Computer Science, 6845 . pp. 111-122. ISSN 0302-9743

Garg, Naveen ; Kavitha, Telikepalli ; Kumar, Amit ; Mehlhorn, Kurt ; Mestre, Julián (2010) Assigning Papers to Referees Algorithmica, 58 (1). pp. 119-136. ISSN 0178-4617

Kumar, Amit ; Kannan, Ravindran (2010) Clustering with Spectral Norm and the k-means Algorithm In: 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 23-26 Oct. 2010, Las Vegas, NV, USA.

Gupta, Anupam ; Krishnaswamy, Ravishankar ; Kumar, Amit ; Segev, Danny (2009) Scheduling with Outliers Lecture Notes in Computer Science, 5687 . pp. 149-162. ISSN 0302-9743

Chadha, Jivitej S. ; Garg, Naveen ; Kumar, Amit ; Muralidhara, V. N. (2009) A competitive algorithm for minimizing weighted flow time on unrelatedmachines with speed augmentation In: STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing, 31 May 2009- 2 June 2009, Bethesda MD USA.

Gupta, Anupam ; Kumar, Amit (2009) A constant-factor approximation for stochastic Steiner forest In: STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing, 31 May 2009- 2 June 2009, Bethesda MD USA.

Golovin, Daniel ; Gupta, Anupam ; Kumar, Amit ; Tangwongsan, Kanat (2008) All-Norms and All-L_p-Norms Approximation Algorithms In: Foundations of Software Technology and Theoretical Computer Science (Bangalore) 2008, 2008.

Garg, Naveen ; Kumar, Amit ; Muralidhara, V. N. (2008) Minimizing Total Flow-Time: The Unrelated Case Lecture Notes in Computer Science, 5369 . pp. 424-435. ISSN 0302-9743

Chakrabarti, Amit ; Chekuri, Chandra ; Gupta, Anupam ; Kumar, Amit (2007) Approximation Algorithms for the Unsplittable Flow Problem Algorithmica, 47 (1). pp. 53-78. ISSN 0178-4617

Garg, Naveen ; Kumar, Amit (2007) Minimizing Average Flow-time : Upper and Lower Bounds In: 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), 21-23 Oct. 2007, Providence, RI, USA.

Breitbart, Yuri ; Garofalakis, Minos ; Gupta, Anupam ; Kumar, Amit ; Rastogi, Rajeev (2007) On Configuring BGP Route Reflectors In: 2007 2nd International Conference on Communication Systems Software and Middleware, 7-12 January 2007, Bangalore, India.

Garg, Naveen ; Kumar, Amit ; Pandit, Vinayaka (2007) Order Scheduling Models: Hardness and Algorithms Lecture Notes in Computer Science, 4855 . pp. 96-107. ISSN 0302-9743

Kumar, Amit ; Sabharwal, Yogish (2007) The Priority k-Median Problem Lecture Notes in Computer Science, 4855 . pp. 71-83. ISSN 0302-9743

Gupta, Anupam ; Hajiaghayi, MohammadTaghi ; Kumar, Amit (2007) Stochastic Steiner Tree with Non-uniform Inflation Lecture Notes in Computer Science, 4627 . pp. 134-148. ISSN 0302-9743

Garg, Naveen ; Kumar, Amit (2006) Better Algorithms for Minimizing Average Flow-Time on Related Machines Lecture Notes in Computer Science, 4051 . pp. 181-190. ISSN 0302-9743

Garg, Naveen ; Kumar, Amit (2006) Better Algorithms for Minimizing Average Flow-Time on Related Machines Lecture Notes in Computer Science, 4051 . pp. 181-190. ISSN 0302-9743

Kumar, Amit ; Kleinberg, Jon (2006) Fairness Measures for Resource Allocation SIAM Journal on Computing, 36 (3). pp. 657-680. ISSN 0097-5397

Chekuri, Chandra ; Gupta, A. ; Kumar, Amit ; Naor, J. ; Raz, Danny (2005) Building Edge-Failure Resilient Networks Algorithmica, 43 (1-2). pp. 17-41. ISSN 0178-4617

Ganguly, Sumit ; Garofalakis, Minos ; Kumar, Amit ; Rastogi, Rajeev (2005) Join-distinct aggregate estimation over update streams In: PODS '05: Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13 - 15, 2005, Baltimore Maryland.

Kumar, Amit ; Sabharwal, Yogish ; Sen, Sandeep (2005) Linear Time Algorithms for Clustering Problems in Any Dimensions Lecture Notes in Computer Science, 3580 . pp. 1374-1385. ISSN 0302-9743

Chekuri, Chandra ; Gupta, Anupam ; Kumar, Amit (2005) On a bidirected relaxation for the MULTIWAY CUT problem Discrete Applied Mathematics, 150 (1-3). pp. 67-79. ISSN 0166-218X

Gupta, Anupam ; Kumar, Amit (2005) Where’s the Winner? Max-Finding and Sorting with Metric Costs Lecture Notes in Computer Science, 3624 . pp. 74-85. ISSN 0302-9743

Garofalakis, Minos ; Kumar, Amit (2004) Deterministic wavelet thresholding for maximum-error metrics In: PODS '04: Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14 - 16, 2004, Paris France.

Chekuri, Chandra ; Kumar, Amit (2004) Maximum Coverage Problem with Group Budget Constraints and Applications Lecture Notes in Computer Science, 3122 . pp. 72-83. ISSN 0302-9743

Chekuri, Chandra ; Goel, Ashish ; Khanna, Sanjeev ; Kumar, Amit (2004) Multi-processor scheduling to minimize flow time with ε resource augmentation In: STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13 - 16, 2004, Chicago IL USA.

Swamy, Chaitanya ; Kumar, Amit (2004) Primal–Dual Algorithms for Connected Facility Location Problems Algorithmica, 40 (4). pp. 245-269. ISSN 0178-4617

Kumar, A. ; Sabharwal, Y. ; Sen, S. (2004) A Simple Linear Time (1+ ∊) -Approximation Algorithm for k-Means Clustering in Any Dimensions In: 45th Annual IEEE Symposium on Foundations of Computer Science, 17-19 Oct. 2004, Rome, Italy.

Gupta, A. ; Kumar, A. ; Pal, M. ; Roughgarden, T. (2003) Approximation via cost-sharing: a simple approximation algorithm for the multicommodity rent-or-buy problem In: 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings, 11-14 Oct. 2003, Cambridge, MA, USA.

Garofalakis, Minos ; Kumar, Amit (2003) Correlating XML data streams using tree-edit distance embeddings In: PODS '03: Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 9 - 11, 2003, San Diego California.

Gupta, Anupam ; Kumar, Amit ; Rastogi, Rajeev (2003) Exploring the trade-off between label size and stack depth in MPLS routing In: IEEE INFOCOM 2003. Twenty-second Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE Cat. No.03CH37428), 30 March-3 April 2003, San Francisco, CA, USA.

Rastogi, R. ; Breitbart, Y. ; Garofalakis, M. ; Kumar, A. (2003) Optimal configuration of OSPF aggregates IEEE/ACM Transactions on Networking, 11 (2). pp. 181-194. ISSN 1063-6692

Gupta, Anupam ; Kumar, Amit ; Roughgarden, Tim (2003) Simpler and better approximation algorithms for network design In: STOC '03: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 9 - 11, 2003, San Diego CA USA.

Kumar, A. ; Rastogi, R. ; Silberschatz, A. ; Yener, B. (2002) Algorithms for provisioning virtual private networks in the hose model IEEE/ACM Transactions on Networking, 10 (4). pp. 565-578. ISSN 1063-6692

Kempe, David ; Kleinberg, Jon ; Kumar, Amit (2002) Connectivity and Inference Problems for Temporal Networks Journal of Computer and System Sciences, 64 (4). pp. 820-842. ISSN 0022-0000

Kumar, A. ; Gupta, A. ; Roughgarden, T. (2002) A constant-factor approximation algorithm for the multicommodity rent-or-buy problem In: The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., 19-19 Nov. 2002, Vancouver, BC, Canada.

Gupta, Anupam ; Kleinberg, Jon ; Kumar, Amit ; Rastogi, Rajeev ; Yener, Bulent (2001) Provisioning a virtual private network In: STOC '01: Proceedings of the thirty-third annual ACM symposium on Theory of computing.

Gupta, A. ; Kumar, A. (2001) Sorting and selection with structured costs In: Proceedings 42nd IEEE Symposium on Foundations of Computer Science, 8-11 Oct. 2001, Newport Beach, CA, USA.

Gupta, A. ; Kumar, A. ; Rastogi, R. (2001) Traveling with a Pez dispenser (or, routing issues in MPLS) In: Proceedings 42nd IEEE Symposium on Foundations of Computer Science, 8-11 Oct. 2001, Newport Beach, CA, USA.

Kleinberg, Jon ; Kumar, Amit (2001) Wavelength Conversion in Optical Networks Journal of Algorithms, 38 (1). pp. 25-50. ISSN 0196-6774

Gu, Albert ; Gupta, Anupam ; Kumar, Amit (1982) The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online In: STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing.