Nikhil Kumar

Research Interests

Approximation Algorithms, Combinatorial Optimization, Graph Algorithms

Teaching

Combinatorial Optimization :  Winter Semester 2021

Approximation Algorithms :  Summer Semester 2022

Publications

2023

•  

  Friedrich, Tobias; Issac, Davis; Kumar, Nikhil; Mallek, Nadym; Zeif, ZienaApproximate Max-Flow Min-Multicut Theorem for Graphs of Bounded TreewidthSymposium Theory of Computing (STOC) 2023: 1325–1334

  [ ][ ][ URL ][ DOI ][ Download ]

2022

•  

  Friedrich, Tobias; Issac, Davis; Kumar, Nikhil; Mallek, Nadym; Zeif, ZienaA Primal-Dual Algorithm for Multicommodity Flows and Multicuts in Treewidth-2 GraphsApproximation Algorithms for Combinatorial Optimization Problems (APPROX) 2022: 55:1–55:18

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Kumar, NikhilAn Approximate Generalization of the Okamura-Seymour TheoremSymposium on Foundations of Computer Science (FOCS) 2022

  [ ][ ][ Download ]

2021

•  

  Antoniadis, Antonios; Kumar, Gunjan; Kumar, NikhilSkeletons and Minimum Energy SchedulingInternational Symposium on Algorithms and Computation (ISAAC) 2021: 51:1–51:16

  [ ][ ][ URL ][ DOI ][ Download ]

2020

•  

  Das, Syamantak; Jain, Lavina; Kumar, NikhilA Constant Factor Approximation for Capacitated Min-Max Tree CoverApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM) 2020: 55:1–55:13

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Garg, Naveen; Kumar, NikhilDual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral FlowEuropean Symposium on Algorithms (ESA) 2020: 55:1–55:13

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Garg, Naveen; Kumar, Nikhil; Sebö, AndrásInteger Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-ApproximationInteger Programming and Combinatorial Optimization (IPCO) 2020: 144–157

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Kumar, NikhilMulticommodity Flows in Planar Graphs with Demands on FacesInternational Symposium on Algorithms and Computation (ISAAC) 2020: 1–11

  [ ][ ][ DOI ][ Download ]

•  

  Antoniadis, Antonios; Garg, Naveen; Kumar‎, Gunjan; Kumar, NikhilParallel Machine Scheduling to Minimize Energy ConsumptionSymposium on Discrete Algorithms (SODA) 2020: 2758–2769

  [ ][ ][ URL ][ DOI ][ Download ]

2019

•  

  Batra, Sanjit Singh; Kumar, Nikhil; Tripathi, AmitabhaSome Problems Concerning the Frobenius Number for Extensions of an Arithmetic ProgressionThe Ramanujan Journal 2019: 545–565

  [ ][ ][ Download ]

2015

•  

  Batra, Sanjit Singh; Kumar, Nikhil; Tripathi, AmitabhaOn a Linear Diophantine Problem Involving the Fibonacci and Lucas SequencesIntegers 2015: A26

  [ ][ ][ URL ][ Download ]