| Publication | Date of Publication | Type |
|---|
| On packing low-diameter spanning trees | 2026-03-18 | Paper |
| A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond | 2025-08-12 | Paper |
| Towards better approximation of graph crossing number | 2025-08-12 | Paper |
| On approximating maximum independent set of rectangles | 2025-08-06 | Paper |
| A polylogarithmic approximation algorithm for edge-disjoint paths with congestion 2 | 2025-05-05 | Paper |
| A faster combinatorial algorithm for maximum bipartite matching | 2024-11-28 | Paper |
| A new conjecture on hardness of 2-CSP's with implications to hardness of densest \(k\)-subgraph and other problems | 2024-09-25 | Paper |
| A distanced matching game, decremental APSP in expanders, and faster deterministic algorithms for graph cut problems | 2024-05-14 | Paper |
| A new deterministic algorithm for fully dynamic all-pairs shortest paths | 2024-05-08 | Paper |
scientific article; zbMATH DE number 7789148 (Why is no real title available?)
Theory of Computing | 2024-01-16 | Paper |
scientific article; zbMATH DE number 7788485 (Why is no real title available?)
(available as arXiv preprint) | 2024-01-15 | Paper |
A subpolynomial approximation algorithm for graph crossing number in low-degree graphs
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
Decremental all-pairs shortest paths in deterministic near-linear time
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
scientific article; zbMATH DE number 7758335 (Why is no real title available?)
(available as arXiv preprint) | 2023-10-31 | Paper |
Almost polynomial hardness of node-disjoint paths in grids
Theory of Computing | 2021-10-25 | Paper |
Improved approximation for node-disjoint paths in grids with sources on the boundary
(available as arXiv preprint) | 2021-07-28 | Paper |
Towards tight(er) bounds for the excluded grid theorem
Journal of Combinatorial Theory. Series B | 2021-02-03 | Paper |
New hardness results for routing on disjoint paths
SIAM Journal on Computing | 2021-01-13 | Paper |
A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
Towards tight(er) bounds for the excluded grid theorem
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Almost polynomial hardness of node-disjoint paths in grids
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
| Approximation algorithms and hardness of the \(k\)-route cut problem | 2019-05-10 | Paper |
| Maximum independent set of rectangles | 2019-05-06 | Paper |
On the approximability of some network design problems
ACM Transactions on Algorithms | 2018-11-05 | Paper |
Approximation algorithms and hardness of the \(k\)-route cut problem
ACM Transactions on Algorithms | 2018-10-30 | Paper |
Polynomial bounds for the grid-minor theorem
Journal of the ACM | 2018-08-02 | Paper |
A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2
Journal of the ACM | 2018-08-02 | Paper |
| Flows, cuts and integral routing in graphs -- an approximation algorithmist's perspective | 2017-11-06 | Paper |
Improved bounds for the flat wall theorem
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
Degree-3 treewidth sparsifiers
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
Degree-3 treewidth sparsifiers
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
| On graph crossing number and edge planarization | 2017-09-29 | Paper |
On graph crossing number and edge planarization
(available as arXiv preprint) | 2017-09-29 | Paper |
Improved approximation for node-disjoint paths in planar graphs
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
| On approximating node-disjoint paths in grids | 2017-08-31 | Paper |
New hardness results for routing on disjoint paths
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Routing in undirected graphs with constant congestion
SIAM Journal on Computing | 2016-09-02 | Paper |
| Improved Bounds for the Excluded Grid Theorem | 2016-02-08 | Paper |
New hardness results for congestion minimization and machine scheduling
Journal of the ACM | 2015-12-04 | Paper |
Polynomial flow-cut gaps and hardness of directed cut problems
Journal of the ACM | 2015-11-11 | Paper |
Algorithmic aspects of bandwidth trading
ACM Transactions on Algorithms | 2015-09-02 | Paper |
Excluded grid theorem: improved and simplified
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
Polynomial bounds for the grid-minor theorem
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
Hardness of cut problems in directed graphs
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
| Approximating \(k\)-median with non-uniform capacities | 2014-10-13 | Paper |
| On the approximability of some network design problems | 2014-10-13 | Paper |
Large-treewidth graph decompositions and applications
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2014-08-07 | Paper |
On allocating goods to maximize fairness
2009 50th Annual IEEE Symposium on Foundations of Computer Science | 2014-07-25 | Paper |
An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
2009 50th Annual IEEE Symposium on Foundations of Computer Science | 2014-07-25 | Paper |
An algorithm for the graph crossing number problem
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
| Resource minimization for fire containment | 2014-05-22 | Paper |
Approximation algorithms and hardness of integral concurrent flow
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
Routing in undirected graphs with constant congestion
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
On vertex sparsifiers with Steiner nodes
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
Approximation algorithms for the directed \(k\)-Tour and \(k\)-Stroll problems
Algorithmica | 2013-08-05 | Paper |
Improved hardness results for profit maximization pricing problems with unlimited supply
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2012-11-02 | Paper |
An \(O(k^3\log n)\)-approximation algorithm for vertex-connectivity survivable network design
Theory of Computing | 2012-09-27 | Paper |
Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
Combinatorica | 2011-12-19 | Paper |
Approximation algorithms for the directed \(k\)-tour and \(k\)-stroll problems
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2010-09-10 | Paper |
Low-distortion embeddings of general metrics into the line
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
New hardness results for congestion minimization and machine scheduling
Proceedings of the thirty-sixth annual ACM symposium on Theory of computing | 2010-08-15 | Paper |
Asymmetric \(k\)-center is \(\log{^*}{n}\)-hard to approximate
Proceedings of the thirty-sixth annual ACM symposium on Theory of computing | 2010-08-15 | Paper |
Resource Minimization Job Scheduling
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-10-28 | Paper |
| scientific article; zbMATH DE number 5506208 (Why is no real title available?) | 2009-02-10 | Paper |
| scientific article; zbMATH DE number 5485528 (Why is no real title available?) | 2009-01-05 | Paper |
| scientific article; zbMATH DE number 5485450 (Why is no real title available?) | 2009-01-05 | Paper |
| scientific article; zbMATH DE number 5485449 (Why is no real title available?) | 2009-01-05 | Paper |
Asymmetric <i>k</i> -center is log <sup>*</sup> <i>n</i> -hard to approximate
Journal of the ACM | 2008-12-21 | Paper |
Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems
Mathematics of Operations Research | 2008-05-27 | Paper |
The Hardness of Metric Labeling
SIAM Journal on Computing | 2007-10-22 | Paper |
Covering Problems with Hard Capacities
SIAM Journal on Computing | 2007-05-03 | Paper |
| scientific article; zbMATH DE number 2038752 (Why is no real title available?) | 2004-02-08 | Paper |
