| Publication | Date of Publication | Type |
|---|
Polynomial integrality gap of flow LP for directed Steiner tree
| 2024-07-19 | Paper |
Almost tight approximation hardness for single-source directed \(k\)-edge-connectivity
| 2024-06-24 | Paper |
On the approximability of the traveling salesman problem with line neighborhoods
| 2024-05-27 | Paper |
Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs
| 2023-10-31 | Paper |
On approximating degree-bounded network design problems
| 2023-10-31 | Paper |
On a partition LP relaxation for min-cost 2-node connected spanning subgraphs
Operations Research Letters | 2023-07-03 | Paper |
$O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm
SIAM Journal on Computing | 2023-04-28 | Paper |
Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
| 2023-04-15 | Paper |
On approximating degree-bounded network design problems
Algorithmica | 2022-05-03 | Paper |
Survivable Network Design Revisited: Group-Connectivity
| 2022-04-28 | Paper |
Survivable network design for group connectivity in low-treewidth graphs
| 2021-08-04 | Paper |
Approximating spanners and directed Steiner forest. Upper and lower bounds
ACM Transactions on Algorithms | 2021-05-03 | Paper |
On the complexity of closest pair via polar-pair of point-sets
| 2020-08-18 | Paper |
From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
SIAM Journal on Computing | 2020-08-18 | Paper |
On the Parameterized Complexity of Approximating Dominating Set
Journal of the ACM | 2020-02-11 | Paper |
\(O(\log^2 k/\log\log k)\)-approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
New tools and connections for exponential-time approximation
Algorithmica | 2019-09-10 | Paper |
On the parameterized complexity of approximating dominating set
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
Parameters of two-prover-one-round game and the hardness of connectivity problems
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
Graph products revisited: tight approximation hardness of induced matching, poset dimension and more
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-05-15 | Paper |
scientific article; zbMATH DE number 7053371 (Why is no real title available?)
| 2019-05-10 | Paper |
On the complexity of closest pair via polar-pair of point-sets
SIAM Journal on Discrete Mathematics | 2019-03-20 | Paper |
Approximating rooted Steiner networks
ACM Transactions on Algorithms | 2018-10-30 | Paper |
Approximating spanners and directed Steiner forest: upper and lower bounds
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Beyond metric embedding: approximating group Steiner trees on bounded treewidth graphs
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Approximating directed Steiner problems via tree embedding
| 2017-12-19 | Paper |
On survivable set connectivity
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed Steiner tree
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Faster algorithms for semi-matching problems
ACM Transactions on Algorithms | 2016-04-11 | Paper |
An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem
Algorithmica | 2015-09-02 | Paper |
Routing regardless of network stability
Algorithmica | 2015-01-19 | Paper |
Coloring graph powers: graph product bounds and hardness of approximation
Lecture Notes in Computer Science | 2014-03-31 | Paper |
Approximation algorithms for minimum-cost \(k\)-\((S,T)\) connected digraphs
SIAM Journal on Discrete Mathematics | 2014-01-21 | Paper |
A rounding by sampling approach to the minimum size \(k\)-arc connected subgraph problem
Automata, Languages, and Programming | 2013-08-12 | Paper |
A bad example for the iterative rounding method for mincost \(k\)-connected spanning subgraphs
Discrete Optimization | 2013-03-13 | Paper |
An \(O(\log^2{k})\)-approximation algorithm for the \(k\)-vertex connected spanning subgraph problem
SIAM Journal on Computing | 2013-02-04 | Paper |
Routing regardless of network stability
Lecture Notes in Computer Science | 2012-09-25 | Paper |
An improved approximation algorithm for minimum-cost subset \(k\)-connectivity (extended abstract)
Automata, Languages and Programming | 2011-07-06 | Paper |
Faster algorithms for semi-matching problems (extended abstract)
Automata, Languages and Programming | 2010-09-07 | Paper |
scientific article; zbMATH DE number 5485526 (Why is no real title available?)
| 2009-01-05 | Paper |
