1.5k citations · 5.7k across the 60 of their papers we have counts for
15 papers · 1 filter
A Fast Algorithm for Separated Sparsity via Perturbed Lagrangians
Aleksander Mądry, Slobodan Mitrović, Ludwig Schmidt
Sparsity-based methods are widely used in machine learning, statistics, and signal processing. There is now a rich class of structured sparsity approaches that expand the modeling…
k-server via multiscale entropic regularization
Sebastien Bubeck, Michael B. Cohen, James R. Lee +2
We present an -competitive randomized algorithm for the -server problem on hierarchically separated trees (HSTs). This is the first -competitive randomized…
Round Compression for Parallel Matching Algorithms
Artur Czumaj, Jakub Łącki, Aleksander Mądry +3
For over a decade now we have been witnessing the success of {\em massive parallel computation} (MPC) frameworks, such as MapReduce, Hadoop, Dryad, or Spark. One of the reasons for…
Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods
Michael B. Cohen, Aleksander Madry, Dimitris Tsipras +1
In this paper, we study matrix scaling and balancing, which are fundamental problems in scientific computing, with a long line of work on them that dates back to the 1960s. We prov…
Computing Maximum Flow with Augmenting Electrical Flows
Aleksander Madry
We present an -time algorithm for the maximum - flow problem and the minimum - cut problem in directed graphs wit…
Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in Time
Michael B. Cohen, Aleksander Madry, Piotr Sankowski +1
In this paper, we study a set of combinatorial optimization problems on weighted graphs: the shortest path problem with negative weights, the weighted perfect bipartite matching pr…