research
∙
08/22/2023
Linear Programming based Reductions for Multiple Visit TSP and Vehicle Routing Problems
Multiple TSP (mTSP) is a important variant of TSP where a set of k sales...
share
research
∙
08/07/2023
An Improved Approximation Algorithm for the Max-3-Section Problem
We consider the Max-3-Section problem, where we are given an undirected ...
research
∙
11/27/2022
Socially Fair and Hierarchical Facility Location Problems
The classic facility location problem seeks to open a set of facilities ...
research
∙
11/18/2022
Efficient Determinant Maximization for All Matroids
Determinant maximization provides an elegant generalization of problems ...
research
∙
10/11/2022
The IID Prophet Inequality with Limited Flexibility
In online sales, sellers usually offer each potential buyer a posted pri...
research
∙
07/09/2022
Determinant Maximization via Matroid Intersection Algorithms
Determinant maximization problem gives a general framework that models p...
research
∙
06/22/2022
Constant-Factor Approximation Algorithms for Socially Fair k-Clustering
We study approximation algorithms for the socially fair (ℓ_p, k)-cluster...
research
∙
12/01/2021
Robust Online Selection with Uncertain Offer Acceptance
Online advertising has motivated interest in online selection problems. ...
research
∙
07/22/2020
Online Adaptive Bin Packing with Overflow
Motivated by bursty bandwidth allocation and by the allocation of virtua...
research
∙
04/16/2020
Maximizing Determinants under Matroid Constraints
Given vectors v_1,…,v_n∈ℝ^d and a matroid M=([n],I), we study the proble...
research
∙
02/10/2020
On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness
Submodular maximization has been widely studied over the past decades, m...
research
∙
07/25/2019
Integrality Gap of the Vertex Cover Linear Programming Relaxation
We give a characterization result for the integrality gap of the natural...
research
∙
05/07/2019
Online and Offline Greedy Algorithms for Routing with Switching Costs
Motivated by the use of high speed circuit switches in large scale data ...
research
∙
02/28/2019
Fair Dimensionality Reduction and Iterative Rounding for SDPs
We model "fair" dimensionality reduction as an optimization problem. A c...
research
∙
12/19/2018
Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems
Semidefinite programming is a powerful tool in the design and analysis o...
research
∙
10/31/2018
The Price of Fair PCA: One Extra Dimension
We investigate whether the standard dimensionality reduction technique o...
research
∙
09/07/2018
Dynamic Resource Allocation in the Cloud with Near-Optimal Efficiency
Cloud computing has motivated renewed interest in resource allocation pr...
research
∙
07/25/2018
Efficient algorithms for robust submodular maximization under matroid constraints
In this work, we consider robust submodular maximization with matroid co...
research
∙
02/23/2018
Approximate Positively Correlated Distributions and Approximation Algorithms for D-optimal Design
Experimental design is a classical problem in statistics and has also fo...
research
∙
02/22/2018