| Publication | Date of Publication | Type |
|---|
| Nonlinear paging | 2026-01-14 | Paper |
| SSD wear leveling with optimal guarantees | 2024-05-29 | Paper |
| Lossless online rounding for online bipartite matching (despite its impossibility) | 2024-05-14 | Paper |
General Knapsack Problems in a Dynamic Setting
(available as arXiv preprint) | 2023-11-20 | Paper |
| Invited talks | 2023-03-22 | Paper |
Online \(k\)-taxi via double coverage and time-reverse primal-dual
Mathematical Programming. Series A. Series B | 2023-03-14 | Paper |
| A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem | 2023-02-07 | Paper |
Approximating minimum feedback sets and multi-cuts in directed graphs (extended summary)
Integer Programming and Combinatorial Optimization | 2022-08-30 | Paper |
Tight bounds for online weighted tree augmentation
(available as arXiv preprint) | 2022-07-21 | Paper |
Structured Robust Submodular Maximization: Offline and Online Algorithms
INFORMS Journal on Computing | 2022-06-28 | Paper |
Tight bounds for online weighted tree augmentation
Algorithmica | 2022-03-25 | Paper |
An almost optimal approximation algorithm for monotone submodular multiple knapsack
Journal of Computer and System Sciences | 2022-01-31 | Paper |
Online \(k\)-taxi via double coverage and time-reverse primal-dual
Integer Programming and Combinatorial Optimization | 2021-12-21 | Paper |
Dynamic storage allocation with known durations
Algorithms — ESA '97 | 2021-12-20 | Paper |
Timing matters: online dynamics in broadcast games
(available as arXiv preprint) | 2020-06-18 | Paper |
| Correlated Rounding of Multiple Uniform Matroids and Multi-Label Classification | 2020-05-27 | Paper |
\(k\)-servers with a smile: online algorithms via projections
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Submodular maximization with cardinality constraints
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
Competitive analysis via regularization
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
Non-uniform graph partitioning
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
| Partitioning graphs into balanced components | 2019-05-06 | Paper |
| Algorithms for dynamic NFV workload | 2019-01-15 | Paper |
Throughput maximization of real-time scheduling with batching
ACM Transactions on Algorithms | 2018-11-05 | Paper |
On the approximability of some network design problems
ACM Transactions on Algorithms | 2018-11-05 | Paper |
Simplex partitioning via exponential clocks and the multiway-cut problem
SIAM Journal on Computing | 2018-08-03 | Paper |
A polylogarithmic-competitive algorithm for the \(k\)-server problem
Journal of the ACM | 2018-08-02 | Paper |
\(O(\mathrm{depth})\)-competitive algorithm for online multi-level aggregation
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
| Online Semidefinite Programming. | 2017-12-19 | Paper |
A truthful mechanism for value-based scheduling in cloud computing
Theory of Computing Systems | 2017-11-07 | Paper |
A greedy approximation algorithm for minimum-gap scheduling
Journal of Scheduling | 2017-09-01 | Paper |
Non-preemptive buffer management for latency sensitive packets
Journal of Scheduling | 2017-08-25 | Paper |
Approximating the throughput of multiple machines under real-time scheduling
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
Efficient recovery from power outage (extended abstract)
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
Unified algorithms for online learning and competitive analysis
Mathematics of Operations Research | 2016-05-19 | Paper |
Equilibria in online games
SIAM Journal on Computing | 2016-03-23 | Paper |
New hardness results for congestion minimization and machine scheduling
Journal of the ACM | 2015-12-04 | Paper |
A unified approach to approximating resource allocation and scheduling
Journal of the ACM | 2015-10-30 | Paper |
A general approach to online network optimization problems
ACM Transactions on Algorithms | 2015-09-02 | Paper |
Algorithmic aspects of bandwidth trading
ACM Transactions on Algorithms | 2015-09-02 | Paper |
| The directed circular arrangement problem | 2015-08-03 | Paper |
| scientific article; zbMATH DE number 6469194 (Why is no real title available?) | 2015-08-03 | Paper |
| Equilibria in online games | 2014-12-18 | Paper |
A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching
Algorithmica | 2014-12-02 | Paper |
The directed circular arrangement problem
ACM Transactions on Algorithms | 2014-11-18 | Paper |
| On the approximability of some network design problems | 2014-10-13 | Paper |
| Approximating the average response time in broadcast scheduling | 2014-10-13 | Paper |
Competitive algorithms for restricted caching and matroid caching
Algorithms - ESA 2014 | 2014-10-08 | Paper |
A unified approach to approximating resource allocation and scheduling
Proceedings of the thirty-second annual ACM symposium on Theory of computing | 2014-09-26 | Paper |
Fair online load balancing
Journal of Scheduling | 2014-08-18 | Paper |
Simplex partitioning via exponential clocks and the multiway cut problem
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2014-08-07 | Paper |
Min-Max Graph Partitioning and Small Set Expansion
SIAM Journal on Computing | 2014-07-30 | Paper |
Min-Max Graph Partitioning and Small Set Expansion
SIAM Journal on Computing | 2014-07-30 | Paper |
Min-max Graph Partitioning and Small Set Expansion
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
Online node-weighted Steiner tree and related problems
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
A Unified Continuous Greedy Algorithm for Submodular Maximization
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
A Polylogarithmic-Competitive Algorithm for the k-Server Problem
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
| Towards the randomized \(k\)-server conjecture, a primal-dual approach | 2014-05-22 | Paper |
A primal-dual randomized algorithm for weighted paging
Journal of the ACM | 2014-02-17 | Paper |
Approximation algorithms for online weighted rank function maximization under matroid constraints
Automata, Languages, and Programming | 2013-08-12 | Paper |
A greedy approximation algorithm for minimum-gap scheduling
Lecture Notes in Computer Science | 2013-06-07 | Paper |
Topology-aware VM migration in bandwidth oversubscribed datacenter networks
Automata, Languages, and Programming | 2012-11-01 | Paper |
Randomized competitive algorithms for generalized caching
SIAM Journal on Computing | 2012-08-10 | Paper |
The load-distance balancing problem
Networks | 2012-06-18 | Paper |
A truthful mechanism for value-based scheduling in cloud computing
Algorithmic Game Theory | 2011-10-28 | Paper |
Improved approximations for \(k\)-exchange systems (extended abstract)
Algorithms – ESA 2011 | 2011-09-16 | Paper |
Improved competitive ratios for submodular secretary problems (extended abstract)
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2011-08-17 | Paper |
Nonmonotone submodular maximization via a structural continuous greedy algorithm (extended abstract)
Automata, Languages and Programming | 2011-07-06 | Paper |
Online primal-dual algorithms for covering and packing
Mathematics of Operations Research | 2011-04-27 | Paper |
Online time-constrained scheduling in linear and ring networks
Journal of Discrete Algorithms | 2011-01-20 | Paper |
Metrical task systems and the \(k\)-server problem on HSTs
Automata, Languages and Programming | 2010-09-07 | Paper |
Balanced metric labeling
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 |
Non-cooperative cost sharing games via subsidies
Theory of Computing Systems | 2010-08-13 | Paper |
Survivable network design with degree or order constraints
SIAM Journal on Computing | 2010-07-07 | Paper |
The online set cover problem
SIAM Journal on Computing | 2010-04-29 | Paper |
The Design of Competitive Online Algorithms via a Primal—Dual Approach
Foundations and Trends® in Theoretical Computer Science | 2009-06-30 | Paper |
| scientific article; zbMATH DE number 5485510 (Why is no real title available?) | 2009-01-05 | Paper |
Survivable network design with degree or order constraints
Proceedings of the thirty-ninth annual ACM symposium on Theory of computing | 2009-01-05 | Paper |
| scientific article; zbMATH DE number 5485535 (Why is no real title available?) | 2009-01-05 | Paper |
Asymmetric k -center is log * n -hard to approximate
Journal of the ACM | 2008-12-21 | Paper |
An O(log2 k)-Competitive Algorithm for Metric Bipartite Matching
Algorithms – ESA 2007 | 2008-09-25 | Paper |
Cut Problems in Graphs with a Budget Constraint
LATIN 2006: Theoretical Informatics | 2008-09-18 | Paper |
Non-cooperative Cost Sharing Games Via Subsidies
Algorithmic Game Theory | 2008-05-02 | Paper |
Coping with Interference: From Maximum Coverage to Planning Cellular Networks
Approximation and Online Algorithms | 2008-02-21 | Paper |
Traffic engineering of management flows by link augmentations on confluent trees
Theory of Computing Systems | 2008-02-18 | Paper |
Approximating the advertisement placement problem
Journal of Scheduling | 2007-12-20 | Paper |
Cut problems in graphs with a budget constraint
Journal of Discrete Algorithms | 2007-10-30 | 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 |
Real-time scheduling with a budget
Algorithmica | 2007-04-26 | Paper |
Efficient algorithms for shared backup allocation in networks with partial information
Journal of Combinatorial Optimization | 2007-01-05 | Paper |
Algorithms – ESA 2005
Lecture Notes in Computer Science | 2006-06-27 | Paper |
Algorithms – ESA 2005
Lecture Notes in Computer Science | 2006-06-27 | Paper |
Scheduling Split Intervals
SIAM Journal on Computing | 2006-06-01 | Paper |
The Steiner k-Cut Problem
SIAM Journal on Discrete Mathematics | 2006-06-01 | Paper |
Building edge-failure resilient networks
Algorithmica | 2006-03-21 | Paper |
Minimizing Service and Operation Costs of Periodic Scheduling
Mathematics of Operations Research | 2005-11-11 | Paper |
A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem
SIAM Journal on Discrete Mathematics | 2005-09-16 | Paper |
Directed Network Design with Orientation Constraints
SIAM Journal on Discrete Mathematics | 2005-09-16 | Paper |
| scientific article; zbMATH DE number 2119734 (Why is no real title available?) | 2004-11-29 | Paper |
| scientific article; zbMATH DE number 2119735 (Why is no real title available?) | 2004-11-29 | Paper |
| scientific article; zbMATH DE number 2119707 (Why is no real title available?) | 2004-11-29 | Paper |
Admission control in networks with advance reservations
Algorithmica | 2004-11-05 | Paper |
| scientific article; zbMATH DE number 2086937 (Why is no real title available?) | 2004-08-11 | Paper |
| scientific article; zbMATH DE number 2086939 (Why is no real title available?) | 2004-08-11 | Paper |
| scientific article; zbMATH DE number 2086617 (Why is no real title available?) | 2004-08-11 | Paper |
| scientific article; zbMATH DE number 2038752 (Why is no real title available?) | 2004-02-08 | Paper |
| scientific article; zbMATH DE number 2038710 (Why is no real title available?) | 2004-02-08 | Paper |
| scientific article; zbMATH DE number 2038779 (Why is no real title available?) | 2004-02-08 | Paper |
Competitive on-Line switching policies
Algorithmica | 2003-08-17 | Paper |
| A deterministic algorithm for the cost-distance problem | 2003-07-29 | Paper |
New algorithms for related machines with temporary jobs.
Journal of Scheduling | 2003-07-27 | Paper |
| scientific article; zbMATH DE number 1947059 (Why is no real title available?) | 2003-07-07 | Paper |
The budgeted maximum coverage problem
Information Processing Letters | 2002-07-25 | Paper |
| Tree packing and approximating \(k\)-cuts | 2002-06-30 | Paper |
A 2-approximation algorithm for the directed multiway cut problem
SIAM Journal on Computing | 2002-04-23 | Paper |
Approximating the throughput of multiple machines in real-time scheduling
SIAM Journal on Computing | 2002-04-23 | Paper |
On-line load balancing in a hierarchical server topology
SIAM Journal on Computing | 2002-04-23 | Paper |
| Approximation algorithms for the metric labeling problem via a new linear programming formulation | 2002-03-24 | Paper |
Computing an optimal orientation of a balanced decomposition tree for linear arrangement problems
Journal of Graph Algorithms and Applications | 2002-01-07 | Paper |
| scientific article; zbMATH DE number 1445363 (Why is no real title available?) | 2000-10-23 | Paper |
An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
SIAM Journal on Computing | 2000-10-18 | Paper |
Message Multicasting in Heterogeneous Networks
SIAM Journal on Computing | 2000-10-18 | Paper |
Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications
SIAM Journal on Discrete Mathematics | 2000-07-20 | Paper |
| scientific article; zbMATH DE number 1261809 (Why is no real title available?) | 2000-04-26 | Paper |
The Loading Time Scheduling Problem
Journal of Algorithms | 2000-01-01 | Paper |
Dynamic storage allocation with known durations
Discrete Applied Mathematics | 2000-01-01 | Paper |
| scientific article; zbMATH DE number 1303536 (Why is no real title available?) | 1999-08-16 | Paper |
Approximating probability distributions using small sample spaces
Combinatorica | 1999-05-18 | Paper |
Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
SIAM Journal on Computing | 1998-09-20 | Paper |
Scheduled Hot-Potato Routing
Journal of Graph Algorithms and Applications | 1998-07-05 | Paper |
Approximating minimum feedback sets and multicuts in directed graphs
Algorithmica | 1998-01-01 | Paper |
| scientific article; zbMATH DE number 1775430 (Why is no real title available?) | 1998-01-01 | Paper |
| scientific article; zbMATH DE number 1003266 (Why is no real title available?) | 1997-06-01 | Paper |
Constructions of permutation arrays for certain scheduling cost measures
Random Structures & Algorithms | 1996-12-09 | Paper |
Tight Bounds for Dynamic Storage Allocation
SIAM Journal on Discrete Mathematics | 1996-08-13 | Paper |
Flow in Planar Graphs with Multiple Sources and Sinks
SIAM Journal on Computing | 1996-04-11 | Paper |
Approximation Algorithms for Network Design Problems on Bounded Subsets
Journal of Algorithms | 1996-01-01 | Paper |
Routing strategies for fast networks
IEEE Transactions on Computers | 1996-01-01 | Paper |
The probabilistic method yields deterministic parallel algorithms
Journal of Computer and System Sciences | 1995-10-24 | Paper |
| scientific article; zbMATH DE number 742966 (Why is no real title available?) | 1995-04-11 | Paper |
Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
SIAM Journal on Computing | 1995-04-06 | Paper |
The Competitiveness of On-Line Assignments
Journal of Algorithms | 1995-01-01 | Paper |
| scientific article; zbMATH DE number 431512 (Why is no real title available?) | 1994-11-29 | Paper |
Flow in planar graphs with vertex capacities
Algorithmica | 1994-01-01 | Paper |
| scientific article; zbMATH DE number 1003306 (Why is no real title available?) | 1994-01-01 | Paper |
The Lattice Structure of Flow in Planar Graphs
SIAM Journal on Discrete Mathematics | 1993-10-14 | Paper |
Small-Bias Probability Spaces: Efficient Constructions and Applications
SIAM Journal on Computing | 1993-10-10 | Paper |
The greedy algorithm is optimal for on-line edge coloring
Information Processing Letters | 1993-05-16 | Paper |
| scientific article; zbMATH DE number 140465 (Why is no real title available?) | 1993-03-28 | Paper |
Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
Mathematical Programming. Series A. Series B | 1993-01-01 | Paper |
A Linear Time Approach to the Set Maxima Problem
SIAM Journal on Discrete Mathematics | 1992-06-28 | Paper |
Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
IEEE Transactions on Information Theory | 1992-06-28 | Paper |
An efficient parallel algorithm for computing a large independent set in a planar graph
Algorithmica | 1991-01-01 | Paper |
An efficient reconstruction of a graph from its line graph in parallel
Journal of Algorithms | 1990-01-01 | Paper |
Sorting, Minimal Feedback Sets, and Hamilton Paths in Tournaments
SIAM Journal on Discrete Mathematics | 1990-01-01 | Paper |
On separating the EREW and CREW PRAM models
Theoretical Computer Science | 1989-01-01 | Paper |
Fast Parallel Algorithms for Chordal Graphs
SIAM Journal on Computing | 1989-01-01 | Paper |
| scientific article; zbMATH DE number 4064510 (Why is no real title available?) | 1988-01-01 | Paper |
A fast parallel algorithm to color a graph with Δ colors
Journal of Algorithms | 1988-01-01 | Paper |
A fast parallel coloring of planar graphs with five colors
Information Processing Letters | 1987-01-01 | Paper |
