Scholars@Duke
Debmalya Panigrahi

Debmalya Panigrahi

Bishop-MacDermott Family Professor of Computer Science
Computer Science
Campus Box 90129, Durham, NC 27708
308 Research Dr, Campus Box 90129, D203 LSRC Building, Durham, NC 27708

Scholarly Works - Other

Caching with Time Windows and Delays

Other SIAM Journal on Computing · August 2022 Full text Cite

Online Service with Delay

Other ACM Transactions on Algorithms · August 1, 2021 In this article, we introduce the online service with delay problem. In this problem, there are n points in a metric space that issue service requests over time, and there is a server that serves these requests. The goal is to minimize the sum of distance ... Full text Cite

Robust algorithms for TSP and steiner tree

Other Leibniz International Proceedings in Informatics Lipics · June 1, 2020 Robust optimization is a widely studied area in operations research, where the algorithm takes as input a range of values and outputs a single solution that performs well for the entire range. Specifically, a robust algorithm aims to minimize regret, defin ... Full text Cite

Minimizing latency in online ride and delivery services

Other Web Conference 2018 Proceedings of the World Wide Web Conference Www 2018 · April 10, 2018 Motivated by the popularity of online ride and delivery services, we study natural variants of classical multi-vehicle minimum latency problems where the objective is to route a set of vehicles located at depots to serve requests located on a metric space ... Full text Cite

Timing matters: Online dynamics in broadcast games

Other Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics · January 1, 2018 This paper studies the equilibrium states that can be reached in a network design game via natural game dynamics. First, we show that an arbitrarily interleaved sequence of arrivals and departures of players can lead to a polynomially inefficient solution ... Full text Cite

Online Covering with Convex Objectives and Applications

Other · December 10, 2014 We give an algorithmic framework for minimizing general convex objectives (that are differentiable and monotone non-decreasing) over a set of covering constraints that arrive online. This substantially extends previous work on online covering for linear ob ... Link to item Cite

Online Algorithms for Machine Minimization

Other · March 3, 2014 In this paper, we consider the online version of the machine minimization problem (introduced by Chuzhoy et al., FOCS 2004), where the goal is to schedule a set of jobs with release times, deadlines, and processing lengths on a minimum number of identical ... Link to item Cite

Online Load Balancing on Unrelated Machines with Startup Costs

Other · March 20, 2012 Motivated by applications in energy-efficient scheduling in data centers, Khuller, Li, and Saha introduced the {\em machine activation} problem as a generalization of the classical optimization problems of set cover and load balancing on unrelated machines ... Link to item Cite

A Linear-time Algorithm for Sparsification of Unweighted Graphs

Other · May 5, 2010 Given an undirected graph $G$ and an error parameter $ε> 0$, the {\em graph sparsification} problem requires sampling edges in $G$ and giving the sampled edges appropriate weights to obtain a sparse graph $G_ε$ with the following property: the weight of ev ... Link to item Cite