26 citations · 64 across the 9 of their papers we have counts for
11 papers
Arrival-Time Incentive Compatibility in Random Order Online Bipartite Matching
Arghya Chakraborty, Varun Gupta
In this work we initiate the study of competitive algorithms with arrival-time incentive compatibility for random-order online bipartite matching in settings where the users care o…
Online Stabilization of Unknown Linear Time-Varying Systems
Jing Yu, Varun Gupta, Adam Wierman
This paper studies the problem of online stabilization of an unknown discrete-time linear time-varying (LTV) system under bounded non-stochastic (potentially adversarial) disturban…
Heavy Traffic Analysis of Multi-Class Bipartite Queueing Systems Under FCFS
Lisa Aoki Hillas, Rene Caldentey, Varun Gupta
This paper examines the performance of multi-class multi-server bipartite queueing systems under a FCFS-ALIS service discipline, where each arriving customer is only compatible wit…
Greedy Algorithm for Multiway Matching with Bounded Regret
Varun Gupta
In this paper we prove the efficacy of a simple greedy algorithm for a finite horizon online resource allocation/matching problem, when the corresponding static planning linear pro…
Approximation Schemes for Multiperiod Binary Knapsack Problems
Zuguang Gao, John R. Birge, Varun Gupta
An instance of the multiperiod binary knapsack problem (MPBKP) is given by a horizon length , a non-decreasing vector of knapsack sizes where denotes…
PERMUTATION Strikes Back: The Power of Recourse in Online Metric Matching
Varun Gupta, Ravishankar Krishnaswamy, Sai Sandeep
In the classical Online Metric Matching problem, we are given a metric space with servers. A collection of clients arrive in an online fashion, and upon arrival, a client shoul…
Load Balancing in the Non-Degenerate Slowdown Regime
Varun Gupta, Neil Walton
We analyse Join-the-Shortest-Queue in a contemporary scaling regime known as the Non-Degenerate Slowdown regime. Join-the-Shortest-Queue (JSQ) is a classical load balancing policy…
Greed Works -- Online Algorithms For Unrelated Machine Stochastic Scheduling
Varun Gupta, Benjamin Moseley, Marc Uetz +1
This paper establishes performance guarantees for online algorithms that schedule stochastic, nonpreemptive jobs on unrelated machines to minimize the expected total weighted compl…
Approximations and Optimal Control for State-dependent Limited Processor Sharing Queues
Varun Gupta, Jiheng Zhang
The paper studies approximations and control of a processor sharing (PS) server where the service rate depends on the number of jobs occupying the server. The control of such a sys…
Online Stochastic Bin Packing
Varun Gupta, Ana Radovanovic
Bin packing is an algorithmic problem that arises in diverse applications such as remnant inventory systems, shipping logistics, and appointment scheduling. In its simplest variant…
Stability of the bipartite matching model
Ana Bušić, Varun Gupta, Jean Mairesse
We consider the bipartite matching model of customers and servers introduced by Caldentey, Kaplan, and Weiss (Adv. Appl. Probab., 2009). Customers and servers play symmetrical role…