research
∙
08/09/2023
Controlling Tail Risk in Online Ski-Rental
The classical ski-rental problem admits a textbook 2-competitive determi...
share
research
∙
08/03/2023
One Partition Approximating All ℓ_p-norm Objectives in Correlation Clustering
This paper considers correlation clustering on unweighted complete graph...
research
∙
05/25/2023
Online Dynamic Acknowledgement with Learned Predictions
We revisit the online dynamic acknowledgment problem. In the problem, a ...
research
∙
05/17/2023
Online List Labeling with Predictions
A growing line of work shows how learned predictions can be used to brea...
research
∙
03/27/2023
Online k-Median with Consistent Clusters
We consider the online k-median clustering problem in which n points arr...
research
∙
03/01/2023
Predictive Flows for Faster Ford-Fulkerson
Recent work has shown that leveraging learned predictions can improve th...
research
∙
01/30/2023
Fast Combinatorial Algorithms for Min Max Correlation Clustering
We introduce fast algorithms for correlation clustering with respect to ...
research
∙
12/15/2022
Min-max Submodular Ranking for Multiple Agents
In the submodular ranking (SR) problem, the input consists of a set of s...
research
∙
11/15/2022
Optimizing Polymatroid Functions
We consider a class of optimization problems that involve determining th...
research
∙
10/22/2022
Algorithms with Prediction Portfolios
The research area of algorithms with predictions has seen recent success...
research
∙
08/29/2022
Configuration Balancing for Stochastic Requests
The configuration balancing problem with stochastic requests generalizes...
research
∙
08/29/2022
Minimizing Completion Times for Stochastic Jobs via Batched Free Times
We study the classic problem of minimizing the expected total completion...
research
∙
06/26/2022
On the Impossibility of Decomposing Binary Matroids
We show that there exist k-colorable matroids that are not (b,c)-decompo...
research
∙
12/10/2021
Learning-Augmented Algorithms for Online Steiner Tree
This paper considers the recently popular beyond-worst-case algorithm an...
research
∙
11/12/2021
A Competitive Algorithm for Throughout Maximization on Identical Machines
This paper considers the basic problem of scheduling jobs online with pr...
research
∙
07/20/2021
Faster Matchings via Learned Duals
A recent line of research investigates how algorithms can be augmented w...
research
∙
07/08/2021
An Efficient Reduction of a Gammoid to a Partition Matroid
Our main contribution is a polynomial-time algorithm to reduce a k-color...
research
∙
06/02/2021
Using Predicted Weights for Ad Delivery
We study the performance of a proportional weights algorithm for online ...
research
∙
12/15/2020
Instance Optimal Join Size Estimation
We consider the problem of efficiently estimating the size of the inner ...
research
∙
11/23/2020
Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing
This paper proposes a new model for augmenting algorithms with useful pr...
research
∙
09/02/2020
Structural Iterative Rounding for Generalized k-Median Problems
This paper considers approximation algorithms for generalized k-median p...
research
∙
08/30/2020
An Objective for Hierarchical Clustering in Euclidean Space and its Connection to Bisecting K-means
This paper explores hierarchical clustering in the case where pairs of p...
research
∙
08/01/2020
Relational Algorithms for k-means Clustering
The majority of learning tasks faced by data scientists involve relation...
research
∙
06/18/2020
Fair Hierarchical Clustering
As machine learning has become more prevalent, researchers have begun to...
research
∙
05/25/2020
Symmetric Linear Programming Formulations for Minimum Cut with Applications to TSP
We introduce multiple symmetric LP relaxations for minimum cut problems....
research
∙
05/19/2020
Optimal Resource Allocation for Elastic and Inelastic Jobs
Modern data centers are tasked with processing heterogeneous workloads c...
research
∙
05/11/2020
A Relational Gradient Descent Algorithm For Support Vector Machine Training
We consider gradient descent like algorithms for Support Vector Machine ...
research
∙
03/24/2020
Approximate Aggregate Queries Under Additive Inequalities
We consider the problem of evaluating certain types of functional aggreg...
research
∙
03/05/2020
Fast Noise Removal for k-Means Clustering
This paper considers k-means clustering in the presence of noise. It is ...
research
∙
01/21/2020
Scheduling for Weighted Flow and Completion Times in Reconfigurable Networks
New optical technologies offer the ability to reconfigure network topolo...
research
∙
01/19/2020
Dynamic Weighted Fairness with Minimal Disruptions
In this paper, we consider the following dynamic fair allocation problem...
research
∙
04/21/2019
Scheduling to Approximate Minimization Objectives on Identical Machines
This paper considers scheduling on identical machines. The scheduling ob...
research
∙
04/18/2019
A Conditional Lower Bound on Graph Connectivity in MapReduce
MapReduce (and its open source implementation Hadoop) has become the de ...
research
∙
01/23/2019
Backprop with Approximate Activations for Memory-efficient Network Training
Larger and deeper neural network architectures deliver improved accuracy...
research
∙
12/22/2018
On Functional Aggregate Queries with Additive Inequalities
Motivated by fundamental applications in databases and relational machin...
research
∙
11/21/2018
Efficient nonmyopic active search with applications in drug and materials discovery
Active search is a learning paradigm for actively identifying as many me...
research
∙
10/07/2018
Pre-Synaptic Pool Modification (PSPM): A Supervised Learning Procedure for Spiking Neural Networks
A central question in neuroscience is how to develop realistic models th...
research
∙
04/23/2018
Online Non-Preemptive Scheduling to Minimize Weighted Flow-time on Unrelated Machines
In this paper, we consider the online problem of scheduling independent ...
research
∙
02/28/2018
Online Non-preemptive Scheduling on Unrelated Machines with Rejections
When a computer system schedules jobs there is typically a significant c...
research
∙
04/22/2013