research
∙
09/18/2023
Maintaining Matroid Intersections Online
Maintaining a maximum bipartite matching online while minimizing recours...
share
research
∙
04/19/2023
The Price of Explainability for Clustering
Given a set of points in d-dimensional space, an explainable clustering ...
research
∙
04/04/2023
Set Covering with Our Eyes Wide Shut
In the stochastic set cover problem (Grandoni et al., FOCS '08), we are ...
research
∙
12/29/2022
Graph Searching with Predictions
Consider an agent exploring an unknown graph in search of some goal stat...
research
∙
11/08/2022
A Local Search-Based Approach for Set Covering
In the Set Cover problem, we are given a set system with each set having...
research
∙
11/08/2022
Optimal shepherding and transport of a flock
We investigate how a shepherd should move in order to effectively herd a...
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
∙
12/24/2021
Robust Secretary and Prophet Algorithms for Packing Integer Programs
We study the problem of solving Packing Integer Programs (PIPs) in the o...
research
∙
11/17/2021
Matroid-Based TSP Rounding for Half-Integral Solutions
We show how to round any half-integral solution to the subtour-eliminati...
research
∙
11/17/2021
A Hitting Set Relaxation for k-Server and an Extension to Time-Windows
We study the k-server problem with time-windows. In this problem, each r...
research
∙
11/12/2021
Random Order Set Cover is as Easy as Offline
We give a polynomial-time algorithm for OnlineSetCover with a competitiv...
research
∙
11/11/2021
Online Discrepancy with Recourse for Vectors and Graphs
The vector-balancing problem is a fundamental problem in discrepancy the...
research
∙
11/10/2021
Non-Adaptive Stochastic Score Classification and Explainable Halfspace Evaluation
We consider the stochastic score classification problem. There are sever...
research
∙
11/08/2021
An Improved Local Search Algorithm for k-Median
We present a new local-search algorithm for the k-median clustering prob...
research
∙
11/03/2021
Probing to Minimize
We develop approximation algorithms for set-selection problems with dete...
research
∙
07/13/2021
Bag-of-Tasks Scheduling on Related Machines
We consider online scheduling to minimize weighted completion time on re...
research
∙
06/30/2021
The Power of Adaptivity for Stochastic Submodular Cover
In the stochastic submodular cover problem, the goal is to select a subs...
research
∙
05/31/2021
A Quasipolynomial (2+ε)-Approximation for Planar Sparsest Cut
The (non-uniform) sparsest cut problem is the following graph-partitioni...
research
∙
04/15/2021
Lipschitz Selectors may not Yield Competitive Algorithms for Convex Body Chasing
The current best algorithms for convex body chasing problem in online al...
research
∙
09/02/2020
Structural Iterative Rounding for Generalized k-Median Problems
This paper considers approximation algorithms for generalized k-median p...
research
∙
09/02/2020
Fully-Dynamic Submodular Cover with Bounded Recourse
In submodular covering problems, we are given a monotone, nonnegative su...
research
∙
07/21/2020
Online Carpooling using Expander Decompositions
We consider the online carpooling problem: given n vertices, a sequence ...
research
∙
06/18/2020
Neutralizing Self-Selection Bias in Sampling for Sortition
Sortition is a political system in which decisions are made by panels of...
research
∙
06/17/2020
Caching with Time Windows and Delays
We consider two generalizations of the classical weighted paging problem...
research
∙
05/28/2020
Dimension-Free Bounds on Chasing Convex Functions
We consider the problem of chasing convex functions, where functions arr...
research
∙
05/17/2020
Optimal Bounds for the k-cut Problem
In the k-cut problem, we want to find the smallest set of edges whose de...
research
∙
02/25/2020
Random-Order Models
This chapter introduces the random-order model in online algorithms. In ...
research
∙
02/25/2020
Stochastic Makespan Minimization in Structured Set Systems
We study stochastic combinatorial optimization problems where the object...
research
∙
11/20/2019
The Karger-Stein Algorithm is Optimal for k-cut
In the k-cut problem, we are given an edge-weighted graph and want to fi...
research
∙
11/17/2019
Robust Algorithms for the Secretary Problem
In classical secretary problems, a sequence of n elements arrive in a un...
research
∙
06/02/2019
The Number of Minimum k-Cuts: Improving the Karger-Stein Bound
Given an edge-weighted graph, how many minimum k-cuts can it have? This ...
research
∙
05/28/2019
Chasing Convex Bodies with Linear Competitive Ratio
We study the problem of chasing convex bodies online: given a sequence o...
research
∙
05/06/2019
Non-clairvoyant Precedence Constrained Scheduling
We consider the online problem of scheduling jobs on identical machines,...
research
∙
04/28/2019
Tight FPT Approximations for k-Median and k-Means
We investigate the fine-grained complexity of approximating the classica...
research
∙
04/19/2019
Stochastic Online Metric Matching
We study the minimum-cost metric perfect matching problem under online i...
research
∙
04/15/2019
Stochastic Load Balancing on Unrelated Machines
We consider the problem of makespan minimization on unrelated machines w...
research
∙
03/17/2019
Spatiotemporal Filtering for Event-Based Action Recognition
In this paper, we address the challenging problem of action recognition,...
research
∙
03/16/2019
Spatiotemporal Feature Learning for Event-Based Vision
Unlike conventional frame-based sensors, event-based visual sensors outp...
research
∙
02/22/2019
Better Algorithms for Stochastic Bandits with Adversarial Corruptions
We study the stochastic multi-armed bandits problem in the presence of a...
research
∙
02/21/2019
The Markovian Price of Information
Suppose there are n Markov chains and we need to pay a per-step price to...
research
∙
10/17/2018
k-Servers with a Smile: Online Algorithms via Projections
We consider the k-server problem on trees and HSTs. We give an algorithm...
research
∙
07/21/2018
Faster Exact and Approximate Algorithms for k-Cut
In the k-cut problem, we are given an edge-weighted graph G and an integ...
research
∙
06/22/2018
A Nearly-Linear Bound for Chasing Nested Convex Bodies
Friedman and Linial introduced the convex body chasing problem to explor...
research
∙
05/24/2018
Non-Preemptive Flow-Time Minimization via Rejections
We consider the online problem of minimizing weighted flow-time on unrel...
research
∙
04/22/2018
Maximizing Profit with Convex Costs in the Random-order Model
Suppose a set of requests arrives online: each request gives some value ...
research
∙
04/04/2018
Losing Treewidth by Separating Subsets
We study the problem of deleting the smallest set S of vertices (resp.ed...
research
∙
12/13/2017
Potential-Function Proofs for First-Order Methods
This note discusses proofs for convergence of first-order methods based ...
research
∙
11/06/2017
Fully-Dynamic Bin Packing with Limited Repacking
We consider the bin packing problem in a fully-dynamic setting, where ne...
research
∙
06/04/2017