| Publication | Date of Publication | Type |
|---|
2-approximation for prize-collecting Steiner forest
| 2024-11-28 | Paper |
Dynamic algorithms for matroid submodular maximization
| 2024-11-28 | Paper |
Power of posted-price mechanisms for prophet inequalities
| 2024-11-28 | Paper |
Prophet secretary for combinatorial auctions and matroids
SIAM Journal on Computing | 2024-11-20 | Paper |
Weighted edit distance computation: strings, trees, and Dyck
| 2024-05-08 | Paper |
scientific article; zbMATH DE number 7829315 (Why is no real title available?)
| 2024-04-09 | Paper |
Brief Announcement: Improved Consensus in Quantum Networks
Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing | 2024-03-26 | Paper |
Improved communication complexity of fault-tolerant consensus
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce
Journal of the ACM | 2022-12-08 | Paper |
Approximating longest common subsequence in linear time: beating the \(\sqrt{n}\) barrier
SIAM Journal on Computing | 2022-08-25 | Paper |
scientific article; zbMATH DE number 7525452 (Why is no real title available?)
| 2022-05-11 | Paper |
Fair allocation of indivisible goods: beyond additive valuations
Artificial Intelligence | 2022-03-02 | Paper |
Lower bounds for external memory integer sorting via network coding
SIAM Journal on Computing | 2021-10-18 | Paper |
Fair allocation of indivisible goods: improvement
Mathematics of Operations Research | 2021-09-14 | Paper |
Greedy algorithms for online survivable network design
| 2021-07-28 | Paper |
Brief announcement: MapReduce algorithms for massive trees
| 2021-07-28 | Paper |
Massively Parallel Computation of Matching and MIS in Sparse Graphs
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing | 2021-01-20 | Paper |
Stochastic matching with few queries: (1-ε) approximation
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
scientific article; zbMATH DE number 7204578 (Why is no real title available?)
| 2020-05-27 | Paper |
From duels to battlefields: computing equilibria of Blotto and other games
Mathematics of Operations Research | 2020-04-30 | Paper |
Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
SIAM Journal on Computing | 2020-03-27 | Paper |
Approximation algorithms for connected maximum cut and related problems
Theoretical Computer Science | 2020-03-12 | Paper |
Computing Stackelberg equilibria of large general-sum games
| 2020-02-04 | Paper |
Stochastic matching on uniformly sparse graphs
| 2020-02-04 | Paper |
\(1+\varepsilon\) approximation of tree edit distance in quadratic time
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
Lower bounds for external memory integer sorting via network coding
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
Stochastic Matching with Few Queries: New Algorithms and Tools
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Approximating LCS in Linear Time: Beating the √n Barrier
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Massively parallel approximation algorithms for edit distance and longest common subsequence
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Polynomial-time approximation scheme for minimum \(k\)-cut in planar and minor-free graphs
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Disjoint-path facility location: theory and practice
2011 Proceedings of the Thirteenth Workshop on Algorithm Engineering and Experiments (ALENEX) | 2019-09-12 | Paper |
Fast algorithms for knapsack via convolution and prediction
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
| 2019-05-10 | Paper |
A polynomial-time approximation scheme for planar multiway cut
| 2019-05-10 | Paper |
Assignment problem in content distribution networks: unsplittable hard-capacitated facility location
| 2019-05-06 | Paper |
scientific article; zbMATH DE number 7051287 (Why is no real title available?)
| 2019-05-06 | Paper |
Streaming algorithms for estimating the matching size in planar graphs and beyond
ACM Transactions on Algorithms | 2019-03-28 | Paper |
Fair Allocation of Indivisible Goods to Asymmetric Agents
Journal of Artificial Intelligence Research | 2019-01-18 | Paper |
Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics
ACM Transactions on Algorithms | 2018-11-05 | Paper |
Oblivious routing on node-capacitated and directed graphs
ACM Transactions on Algorithms | 2018-11-05 | Paper |
A constant factor approximation algorithm for fault-tolerant \(k\)-median
ACM Transactions on Algorithms | 2018-11-05 | Paper |
Approximation algorithms for movement repairmen
ACM Transactions on Algorithms | 2018-11-05 | Paper |
Node-weighted Steiner tree and group Steiner tree in planar graphs
ACM Transactions on Algorithms | 2018-10-30 | Paper |
Minimizing movement: fixed-parameter tractability
ACM Transactions on Algorithms | 2018-10-30 | Paper |
Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Online degree-bounded Steiner network design
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Improved approximation algorithms for (budgeted) node-weighted Steiner problems
SIAM Journal on Computing | 2018-07-06 | Paper |
scientific article; zbMATH DE number 6850473 (Why is no real title available?)
| 2018-03-15 | Paper |
From battlefields to elections: winning strategies of Blotto and auditing games
| 2018-03-15 | Paper |
Prophet secretary for combinatorial auctions and matroids
| 2018-03-15 | Paper |
Approximating edit distance in truly subquadratic time: quantum and MapReduce
| 2018-03-15 | Paper |
Beating ratio 0.5 for weighted oblivious matching problems
| 2018-03-02 | Paper |
Bicovering: covering edges with two small subsets of vertices
| 2017-12-19 | Paper |
Online weighted degree-bounded Steiner networks via novel online mixed packing/covering
| 2017-12-19 | Paper |
Price of Competition and Dueling Games
| 2017-12-19 | Paper |
Bi-covering: covering edges with two small subsets of vertices
SIAM Journal on Discrete Mathematics | 2017-12-11 | Paper |
On maximum leaf trees and connections to connected maximum cut problems
Information Processing Letters | 2017-10-18 | Paper |
Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
Parameterized Streaming: Maximal Matching and Vertex Cover
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
Capacitated metric labeling
| 2017-09-29 | Paper |
scientific article; zbMATH DE number 6783450 (Why is no real title available?)
| 2017-09-29 | Paper |
Low-dimensional embedding with extra information
Proceedings of the twentieth annual symposium on Computational geometry | 2017-09-29 | Paper |
A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
A greedy approximation algorithm for minimum-gap scheduling
Journal of Scheduling | 2017-09-01 | Paper |
Beating \(1-\frac{1}{e}\) for ordered prophets
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Prophet secretary
SIAM Journal on Discrete Mathematics | 2017-08-14 | Paper |
Online Node-weighted Steiner Forest and Extensions via Disk Paintings
SIAM Journal on Computing | 2017-05-30 | Paper |
A tight algorithm for strongly connected Steiner subgraph on two terminals with demands
Algorithmica | 2017-05-02 | Paper |
Designing FPT algorithms for cut problems using randomized contractions
SIAM Journal on Computing | 2016-08-16 | Paper |
On fixed cost \(k\)-flow problems
Theory of Computing Systems | 2016-03-21 | Paper |
Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
Journal of the ACM | 2015-12-04 | Paper |
Revenue maximization for selling multiple correlated items
Algorithms - ESA 2015 | 2015-11-19 | Paper |
Prophet secretary
Algorithms - ESA 2015 | 2015-11-19 | Paper |
Approximation algorithms for connected maximum cut and related problems
Lecture Notes in Computer Science | 2015-11-19 | Paper |
A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract)
Parameterized and Exact Computation | 2015-09-15 | Paper |
Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
ACM Transactions on Algorithms | 2015-09-02 | Paper |
Equivalence of local treewidth and linear local treewidth and its algorithmic applications
| 2015-08-03 | Paper |
Subexponential parameterized algorithms on graphs of bounded-genus and \(H\)-minor-free graphs
| 2015-08-03 | Paper |
On a local protocol for concurrent file transfers
Theory of Computing Systems | 2015-01-19 | Paper |
Network Cournot competition
Web and Internet Economics | 2015-01-07 | Paper |
Randomized revenue monotone mechanisms for online advertising
Web and Internet Economics | 2015-01-07 | Paper |
Correction: ``Basic network creation games
SIAM Journal on Discrete Mathematics | 2014-12-22 | Paper |
Approximation algorithms for node-weighted buy-at-bulk network design
| 2014-12-18 | Paper |
scientific article; zbMATH DE number 6381654 (Why is no real title available?)
| 2014-12-18 | Paper |
Minimizing movement
| 2014-12-18 | Paper |
Semi-oblivious routing: lower bounds
| 2014-12-18 | Paper |
Submodular secretary problem and extensions
ACM Transactions on Algorithms | 2014-12-05 | Paper |
Prize-collecting steiner network problems
ACM Transactions on Algorithms | 2014-12-05 | Paper |
Minimizing movement
ACM Transactions on Algorithms | 2014-11-18 | Paper |
Dial a ride from \(k\)-forest
ACM Transactions on Algorithms | 2014-11-18 | Paper |
Bidimensionality: new connections between FPT algorithms and PTASs
| 2014-10-13 | Paper |
Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality
| 2014-10-13 | Paper |
Ordinal embeddings of minimum relaxation, general properties, trees, and ultrametrics
| 2014-10-13 | Paper |
Online client-server load balancing without global information
| 2014-10-13 | Paper |
Oblivious routing on node-capacitated and directed graphs
| 2014-10-13 | Paper |
Assignment problem in content distribution networks, unsplittable hard-capacitated facility location
ACM Transactions on Algorithms | 2014-09-09 | Paper |
The price of anarchy in network creation games
ACM Transactions on Algorithms | 2014-09-09 | Paper |
On fixed cost \(k\)-flow problems
Approximation and Online Algorithms | 2014-09-02 | Paper |
Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
Improved Approximation Algorithms for PRIZE-COLLECTING STEINER TREE and TSP
2009 50th Annual IEEE Symposium on Foundations of Computer Science | 2014-07-25 | Paper |
Near-optimal online algorithms for prize-collecting Steiner problems
Automata, Languages, and Programming | 2014-07-01 | Paper |
Online stochastic reordering buffer scheduling
Automata, Languages, and Programming | 2014-07-01 | Paper |
Contraction decomposition in \(h\)-minor-free graphs and algorithmic applications
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
scientific article; zbMATH DE number 6297711 (Why is no real title available?)
| 2014-05-22 | Paper |
The price of anarchy in network creation games
Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing | 2014-03-13 | Paper |
Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
Journal of the ACM | 2014-02-17 | Paper |
Scheduling to minimize gaps and power consumption
Journal of Scheduling | 2014-02-05 | Paper |
Fixed-Parameter and Approximation Algorithms: A New Look
Parameterized and Exact Computation | 2013-12-10 | Paper |
Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
SIAM Journal on Computing | 2013-11-14 | Paper |
Scheduling a cascade with opposing influences
Algorithmic Game Theory | 2013-10-23 | Paper |
The online stochastic generalized assignment problem
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2013-10-04 | Paper |
Approximation algorithms for movement repairmen
Lecture Notes in Computer Science | 2013-10-04 | Paper |
Basic network creation games
SIAM Journal on Discrete Mathematics | 2013-09-26 | Paper |
Directed Subset Feedback Vertex Set is fixed-parameter tractable
Automata, Languages, and Programming | 2013-08-12 | Paper |
Improved approximation algorithms for (budgeted) node-weighted Steiner problems
Automata, Languages, and Programming | 2013-08-06 | Paper |
A greedy approximation algorithm for minimum-gap scheduling
Lecture Notes in Computer Science | 2013-06-07 | Paper |
Approximation algorithms via contraction decomposition
Combinatorica | 2013-04-05 | Paper |
Scheduling to minimize staleness and stretch in real-time data warehouses
Theory of Computing Systems | 2012-12-10 | Paper |
Local search algorithms for the red-blue median problem
Algorithmica | 2012-12-06 | Paper |
The checkpoint problem
Theoretical Computer Science | 2012-10-11 | Paper |
Euclidean prize-collecting Steiner forest
Algorithmica | 2012-04-26 | Paper |
The price of anarchy in cooperative network creation games
| 2012-04-24 | Paper |
AdCell: ad allocation in cellular networks
Algorithms – ESA 2011 | 2011-09-16 | Paper |
Improved approximation algorithms for label cover problems
Algorithmica | 2011-08-16 | Paper |
Improved approximation algorithms for prize-collecting Steiner tree and TSP
SIAM Journal on Computing | 2011-07-29 | Paper |
Approximation algorithms for nonuniform buy-at-bulk network design
SIAM Journal on Computing | 2010-11-04 | Paper |
Submodular secretary problem and extensions
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2010-09-10 | Paper |
The checkpoint problem
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2010-09-10 | Paper |
The cooperative game theory foundations of network bargaining games
Automata, Languages and Programming | 2010-09-07 | Paper |
Budgeted red-blue median and its generalizations
Algorithms – ESA 2010 | 2010-09-06 | Paper |
Improved lower and upper bounds for universal TSP in planar metrics
Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 | 2010-08-16 | Paper |
Oblivious network design
Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 | 2010-08-16 | Paper |
Improved approximation algorithms for minimum-weight vertex separators
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
New lower bounds for oblivious routing in undirected graphs
Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 | 2010-08-16 | Paper |
Combination can be hard
Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 | 2010-08-16 | Paper |
Oblivious routing in directed graphs with random demands
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Prize-collecting Steiner network problems
Integer Programming and Combinatorial Optimization | 2010-06-22 | Paper |
Prize-collecting Steiner networks via iterative rounding
LATIN 2010: Theoretical Informatics | 2010-04-27 | Paper |
Euclidean Prize-Collecting Steiner Forest
LATIN 2010: Theoretical Informatics | 2010-04-27 | Paper |
An \(O(\sqrt n)\)-approximation algorithm for directed sparsest cut
Information Processing Letters | 2009-12-18 | Paper |
A note on the subadditive network design problem
Operations Research Letters | 2009-11-17 | Paper |
Minimizing Movement: Fixed-Parameter Tractability
Lecture Notes in Computer Science | 2009-10-29 | Paper |
Improved Approximation Algorithms for Label Cover Problems
Lecture Notes in Computer Science | 2009-10-29 | Paper |
Combination Can Be Hard: Approximability of the Unique Coverage Problem
SIAM Journal on Computing | 2009-08-20 | Paper |
Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs
Automata, Languages and Programming | 2009-07-14 | Paper |
Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs
Automata, Languages and Programming | 2009-07-14 | Paper |
Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
Algorithmica | 2009-06-22 | Paper |
Hat Guessing Games
SIAM Review | 2009-06-11 | Paper |
Hat Guessing Games
SIAM Journal on Discrete Mathematics | 2009-05-27 | Paper |
Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees
Algorithmica | 2009-05-13 | Paper |
LATIN 2004: Theoretical Informatics
Lecture Notes in Computer Science | 2009-05-07 | Paper |
Improved Approximation Algorithms for Minimum Weight Vertex Separators
SIAM Journal on Computing | 2009-04-30 | Paper |
Stochastic Steiner Tree with Non-uniform Inflation
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-02-17 | Paper |
Plane embeddings of planar graph metrics
| 2009-02-10 | Paper |
scientific article; zbMATH DE number 5485549 (Why is no real title available?)
| 2009-01-05 | Paper |
Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction
Lecture Notes in Computer Science | 2008-11-27 | Paper |
Linearity of grid minors in treewidth with applications through bidimensionality
Combinatorica | 2008-10-21 | Paper |
Dial a Ride from k-Forest
Algorithms – ESA 2007 | 2008-09-25 | Paper |
Localized Client-Server Load Balancing without Global Information
SIAM Journal on Computing | 2008-08-14 | Paper |
Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner’s Contraction
Algorithms and Computation | 2008-04-24 | Paper |
Plane embeddings of planar graph metrics
Discrete & Computational Geometry | 2008-01-04 | Paper |
Power Optimization for Connectivity Problems
Integer Programming and Combinatorial Optimization | 2007-08-30 | Paper |
Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2007-08-28 | Paper |
Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth
Journal of Computer and System Sciences | 2007-05-30 | Paper |
Fast approximation schemes for K3, 3-minor-free or K5-minor-free graphs
Electronic Notes in Discrete Mathematics | 2007-05-29 | Paper |
The Bidimensional Theory of Bounded-Genus Graphs
SIAM Journal on Discrete Mathematics | 2007-05-22 | Paper |
Power optimization for connectivity problems
Mathematical Programming. Series A. Series B | 2007-04-19 | Paper |
Quickly deciding minor-closed parameters in general graphs
European Journal of Combinatorics | 2006-12-07 | Paper |
Low-dimensional embedding with extra information
Discrete & Computational Geometry | 2006-12-06 | Paper |
On the Max-flow min-cut ratio for directed multicommodity flows
Theoretical Computer Science | 2006-03-24 | Paper |
Graph Drawing
Lecture Notes in Computer Science | 2005-12-07 | Paper |
Bidimensional Parameters and Local Treewidth
SIAM Journal on Discrete Mathematics | 2005-09-16 | Paper |
Mathematical Foundations of Computer Science 2004
Lecture Notes in Computer Science | 2005-08-22 | Paper |
Balanced vertex-orderings of graphs
Discrete Applied Mathematics | 2005-05-04 | Paper |
Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors
Algorithmica | 2005-04-29 | Paper |
Diameter and treewidth in minor-closed graph families, revisited
Algorithmica | 2005-02-11 | Paper |
Characterization of networks supporting multi-dimensional linear interval routing schemes
Theoretical Computer Science | 2005-01-11 | Paper |
Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
Journal of Computer and System Sciences | 2004-10-01 | Paper |
Random MAX SAT, random MAX CUT, and their phase transitions
Random Structures & Algorithms | 2004-08-06 | Paper |
scientific article; zbMATH DE number 2079360 (Why is no real title available?)
| 2004-07-28 | Paper |
scientific article; zbMATH DE number 2038758 (Why is no real title available?)
| 2004-02-08 | Paper |
A note on the bounded fragmentation property and its applications in network reliability
European Journal of Combinatorics | 2003-11-16 | Paper |
The Satisfiability Threshold of Random 3-SAT Is at Least 3.52
| 2003-10-13 | Paper |
scientific article; zbMATH DE number 1979505 (Why is no real title available?)
| 2003-09-14 | Paper |
The facility location problem with general cost functions
Networks | 2003-08-20 | Paper |
Palindrome recognition using a multidimensional tape.
Theoretical Computer Science | 2003-08-17 | Paper |
scientific article; zbMATH DE number 1947048 (Why is no real title available?)
| 2003-07-07 | Paper |
scientific article; zbMATH DE number 1929947 (Why is no real title available?)
| 2003-06-18 | Paper |
A note on the consecutive ones submatrix problem.
Information Processing Letters | 2003-01-21 | Paper |
Length-constrained path-matchings in graphs
Networks | 2002-09-29 | Paper |
