research
∙
05/25/2023
Polylogarithmic Approximation for Robust s-t Path
The paper revisits the robust s-t path problem, one of the most fundamen...
share
research
∙
02/22/2023
Degrees and Network Design: New Problems and Approximations
While much of network design focuses mostly on cost (number or weight of...
research
∙
11/29/2022
Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse
We consider the online unrelated-machine load balancing problem with rec...
research
∙
11/18/2022
Improved Approximations for Unrelated Machine Scheduling
We revisit two well-studied scheduling problems in the unrelated machine...
research
∙
07/25/2022
Nested Active-Time Scheduling
The active-time scheduling problem considers the problem of scheduling p...
research
∙
11/09/2021
Nearly-Linear Time Approximate Scheduling Algorithms
We study nearly-linear time approximation algorithms for non-preemptive ...
research
∙
10/29/2021
Online Food Delivery to Minimize Maximum Flow Time
We study a common delivery problem encountered in nowadays online food-o...
research
∙
10/26/2021
Polynomial Integrality Gap of Flow LP for Directed Steiner Tree
In the Directed Steiner Tree (DST) problem, we are given a directed grap...
research
∙
05/14/2021
KIGLIS: Smart Networks for Smart Cities
Smart cities will be characterized by a variety of intelligent and netwo...
research
∙
10/19/2020
Robust High Dimensional Expectation Maximization Algorithm via Trimmed Hard Thresholding
In this paper, we study the problem of estimating latent variable models...
research
∙
10/19/2020
Estimating Stochastic Linear Combination of Non-linear Regressions Efficiently and Scalably
Recently, many machine learning and statistical models such as non-linea...
research
∙
08/13/2020
Consistent k-Median: Simpler, Better and Robust
In this paper we introduce and study the online consistent k-clustering ...
research
∙
04/28/2020
Hierarchy-Based Algorithms for Minimizing Makespan under Precedence and Communication Constraints
We consider the classic problem of scheduling jobs with precedence const...
research
∙
04/02/2020
Towards PTAS for Precedence Constrained Scheduling via Combinatorial Algorithms
We study the classic problem of scheduling n precedence constrained unit...
research
∙
03/21/2020
Covering the Relational Join
In this paper, we initiate a theoretical study of what we call the join ...
research
∙
03/12/2020
Topology Dependent Bounds For FAQs
In this paper, we prove topology dependent bounds on the number of round...
research
∙
02/25/2020
The Power of Recourse: Better Algorithms for Facility Location in Online and Dynamic Models
In this paper we study the facility location problem in the online with ...
research
∙
10/26/2019
Facility Location Problem in Differential Privacy Model Revisited
In this paper we study the uncapacitated facility location problem in th...
research
∙
07/26/2019
Tight Approximation for Variants of Directed Steiner Tree via State-Tree Decomposition and Linear Programming Rounding
Directed Steiner Tree (DST) is a central problem in combinatorial optimi...
research
∙
12/18/2018
Optimizing Data Intensive Flows for Networks on Chips
Data flow analysis and optimization is considered for homogeneous rectan...
research
∙
11/07/2018
O(^2k/k)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm
In the Directed Steiner Tree (DST) problem we are given an n-vertex dire...
research
∙
10/18/2018
Distributed k-Clustering for Data with Heavy Noise
In this paper, we consider the k-center/median/means clustering with out...
research
∙
09/07/2018
Approximation algorithms for stochastic clustering
We consider stochastic settings for clustering, and develop provably-goo...
research
∙
07/25/2018
A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time
We consider the classic scheduling problem of minimizing the total weigh...
research
∙
07/06/2018
Flow-time Optimization For Concurrent Open-Shop and Precedence Constrained Scheduling Models
Scheduling a set of jobs over a collection of machines is a fundamental ...
research
∙
05/06/2018
On Facility Location with General Lower Bounds
In this paper, we give the first constant approximation algorithm for th...
research
∙
11/03/2017