Shi Li

CoRR, 2023

Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse.

[BibT_eX]

[DOI]

Varun Suriyanarayana

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Improved Approximations for Unrelated Machine Scheduling.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Nearly-Linear Time LP Solvers and Rounding Algorithms for Scheduling Problems.

[BibT_eX]

[DOI]

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

On Approximating Degree-Bounded Network Design Problems.

[BibT_eX]

[DOI]

Algorithmica, 2022

Brief Announcement: Nested Active-Time Scheduling.

[BibT_eX]

[DOI]

Proceedings of the SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11, 2022

Polynomial Integrality Gap of Flow LP for Directed Steiner Tree.

[BibT_eX]

[DOI]

Bundit Laekhanukit

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Nested Active-Time Scheduling.

[BibT_eX]

[DOI]

Proceedings of the 33rd International Symposium on Algorithms and Computation, 2022

On Facility Location Problem in the Local Differential Privacy Model.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2022

2021

Online Food Delivery to Minimize Maximum Flow Time.

[BibT_eX]

[DOI]

CoRR, 2021

Towards PTAS for Precedence Constrained Scheduling via Combinatorial Algorithms.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Online Unrelated Machine Load Balancing with Predictions Revisited.

[BibT_eX]

[DOI]

Jiayi Xian

Proceedings of the 38th International Conference on Machine Learning, 2021

Consistent k-Median: Simpler, Better and Robust.

[BibT_eX]

[DOI]

Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, 2021

2020

On the Hardness of Approximating the k-Way Hypergraph Cut problem.

[BibT_eX]

[DOI]

Chandra Chekuri

Theory Comput., 2020

Breaking 1 - 1/e Barrier for Nonpreemptive Throughput Maximization.

[BibT_eX]

[DOI]

Benjamin Moseley

SIAM J. Discret. Math., 2020

Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations.

[BibT_eX]

[DOI]

SIAM J. Comput., 2020

Constant Approximation Algorithm for Nonuniform Capacitated Multi-Item Lot Sizing via Strong Covering Inequalities.

[BibT_eX]

[DOI]

Math. Oper. Res., 2020

Robust high dimensional expectation maximization algorithm via trimmed hard thresholding.

[BibT_eX]

[DOI]

Mach. Learn., 2020

Estimating stochastic linear combination of non-linear regressions efficiently and scalably.

[BibT_eX]

[DOI]

Neurocomputing, 2020

Covering the Relational Join.

[BibT_eX]

[DOI]

Sai Vikneshwar Mani Jayaraman

Atri Rudra

CoRR, 2020

The Power of Recourse: Better Algorithms for Facility Location in Online and Dynamic Models.

[BibT_eX]

[DOI]

CoRR, 2020

Approximating Global Optimum for Probabilistic Truth Discovery.

[BibT_eX]

[DOI]

Jinhui Xu

Minwei Ye

Algorithmica, 2020

Hierarchy-Based Algorithms for Minimizing Makespan under Precedence and Communication Constraints.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

On the Facility Location Problem in Online and Dynamic Models.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2020

Estimating Stochastic Linear Combination of Non-Linear Regressions.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence, 2020

2019

Approximation Algorithms for Stochastic Clustering.

[BibT_eX]

[DOI]

J. Mach. Learn. Res., 2019

Tight Approximation for Variants of Directed Steiner Tree via State-Tree Decomposition and Linear Programming Rounding.

[BibT_eX]

[DOI]

CoRR, 2019

O(log2 k / log log k)-approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm.

[BibT_eX]

[DOI]

Fabrizio Grandoni

Bundit Laekhanukit

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

On Facility Location with General Lower Bounds.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Lift and Project Algorithms for Precedence Constrained Scheduling to Minimize Completion Time.

[BibT_eX]

[DOI]

Shashwat Garg

Janardhan Kulkarni

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time.

[BibT_eX]

[DOI]

Uriel Feige

Janardhan Kulkarni

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Topology Dependent Bounds For FAQs.

[BibT_eX]

[DOI]

Michael Langberg

Sai Vikneshwar Mani Jayaraman

Atri Rudra

Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2019

Facility Location Problem in Differential Privacy Model Revisited.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Automating CSI Measurement with UAVs: from Problem Formulation to Energy-Optimal Solution.

[BibT_eX]

[DOI]

Sixu Piao

Zhongjie Ba

Lu Su

Dimitrios Koutsonikolas

Kui Ren

Proceedings of the 2019 IEEE Conference on Computer Communications, 2019

2018

O(log2k/log log k)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm.

[BibT_eX]

[DOI]

Fabrizio Grandoni

Bundit Laekhanukit

CoRR, 2018

Constant approximation for k-median and k-means with outliers via iterative rounding.

[BibT_eX]

[DOI]

Sai Sandeep

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Distributed k-Clustering for Data with Heavy Noise.

[BibT_eX]

[DOI]

Xiangyu Guo

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Flow-time Optimization for Concurrent Open-Shop and Precedence Constrained Scheduling Models.

[BibT_eX]

[DOI]

Janardhan Kulkarni

Proceedings of the Approximation, 2018

2017

On Uniform Capacitated k-Median Beyond the Natural LP Relaxation.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2017

Constant Approximation Algorithm for Non-Uniform Capacitated Multi-Item Lot-Sizing via Strong Covering Inequalities.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Breaking 1 - 1/e Barrier for Non-preemptive Throughput Maximization.

[BibT_eX]

[DOI]

Mohammad Taghi Hajiaghayi

Benjamin Moseley

Proceedings of the Integer Programming and Combinatorial Optimization, 2017

2016

A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

On the Computational Complexity of Minimum-Concave-Cost Flow in a Two-Dimensional Grid.

[BibT_eX]

[DOI]

SIAM J. Optim., 2016

Approximating k-Median via Pseudo-Approximation.

[BibT_eX]

[DOI]

Ola Svensson

SIAM J. Comput., 2016

A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2.

[BibT_eX]

[DOI]

Julia Chuzhoy

J. ACM, 2016

Tight Network Topology Dependent Bounds on Rounds of Communication.

[BibT_eX]

[DOI]

Arkadev Chattopadhyay

Michael Langberg

Atri Rudra

Electron. Colloquium Comput. Complex., 2016

Constant Approximation for Capacitated k-Median with (1 + ε)-Capacity Violation.

[BibT_eX]

[DOI]

H. Gökalp Demirci

CoRR, 2016

Improved approximation for node-disjoint paths in planar graphs.

[BibT_eX]

[DOI]

Julia Chuzhoy

David H. K. Kim

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Approximating capacitated k-median with (1 + ∊)k open facilities.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Constant Approximation for Capacitated k-Median with (1+epsilon)-Capacity Violation.

[BibT_eX]

[DOI]

H. Gökalp Demirci

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Better Unrelated Machine Scheduling for Weighted Completion Time via Random Offsets from Non-uniform Distributions.

[BibT_eX]

[DOI]

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

Traffic Congestion in Expanders and (p, δ)-Hyperbolic Spaces.

[BibT_eX]

[DOI]

Gabriel H. Tucci

Internet Math., 2015

A Dynamic Programming Framework for Non-Preemptive Scheduling Problems on Multiple Machines [Extended Abstract].

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

On (1, ∊)-Restricted Assignment Makespan Minimization.

[BibT_eX]

[DOI]

Deeparnab Chakrabarty

Sanjeev Khanna

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

2014

Deriving Vegetation Phenological Time and Trajectory Information Over Africa Using SEVIRI Daily LAI.

[BibT_eX]

[DOI]

IEEE Trans. Geosci. Remote. Sens., 2014

Approximating capacitated $k$-median with $(1+ε)k$ open facilities.

[BibT_eX]

[DOI]

CoRR, 2014

On Uniform Capacitated $k$-Median Beyond the Natural LP Relaxation.

[BibT_eX]

[DOI]

CoRR, 2014

On $(1, ε)$-Restricted Assignment Makespan Minimization.

[BibT_eX]

[DOI]

Deeparnab Chakrabarty

Sanjeev Khanna

CoRR, 2014

Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach.

[BibT_eX]

[DOI]

Nikhil Bansal

Moses Charikar

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

2013

A 1.488 approximation algorithm for the uncapacitated facility location problem.

[BibT_eX]

[DOI]

Inf. Comput., 2013

Traffic Congestion in Expanders, $(p,δ)$--Hyperbolic Spaces and Product of Trees

[BibT_eX]

[DOI]

Mohammad Taghi Hajiaghayi

Gabriel H. Tucci

CoRR, 2013

A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median.

[BibT_eX]

[DOI]

CoRR, 2013

Capacitated Network Design on Undirected Graphs.

[BibT_eX]

[DOI]

Deeparnab Chakrabarty

Srivatsan Narayanan

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012

A Polylogarithimic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2

[BibT_eX]

[DOI]

Julia Chuzhoy

CoRR, 2012

Approximation algorithms and hardness of integral concurrent flow.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

A Dependent LP-Rounding Approach for the k-Median Problem.

[BibT_eX]

[DOI]

Moses Charikar

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2010

Multicast Capacity of Wireless Ad Hoc Networks Under Gaussian Channel Model.

[BibT_eX]

[DOI]

IEEE/ACM Trans. Netw., 2010

On constant factor approximation for earth mover distance over doubling metrics

[BibT_eX]

[DOI]