Dr Andreas Feldmann
Department of Computer Science
Senior Lecturer in Algorithms
A.E.Feldmann@sheffield.ac.uk
Regent Court (DCS)
Full contact details
Dr Andreas Feldmann
Department of Computer Science
Regent Court (DCS)
211 Portobello
Sheffield
S1 4DP
Department of Computer Science
Regent Court (DCS)
211 Portobello
Sheffield
S1 4DP
- Profile
-
Dr. habil. Andreas Emil Feldmann attended the European School in Luxemburg, and studied computer science at RWTH Aachen with an Erasmus exchange year at Chalmers University in Gothenburg. He obtained his Diploma in computer science from RWTH Aachen in 2007, and the title of Doctor of Sciences from ETH Zurich in 2012. After that he joined the University of Waterloo as a postdoctoral fellow until 2015, and then spent another year as a postdoctoral fellow at the Hungarian Academy of Sciences. In 2015 he joined Charles University in Prague as an assistant professor, where he successfully defended his habilitation in 2021. Since 2023 he is a senior lecturer at the Department of Computer Science within the Algorithms research group.
- Research interests
-
Combinatorial optimization, parameterized approximation algorithms.
- Publications
-
Journal articles
- Parameterized Inapproximability of Independent Set in H-Free Graphs. Algorithmica, 85(4), 902-928.
- Polynomial time approximation schemes for clustering in low highway dimension graphs. Journal of Computer and System Sciences, 122, 72-93.
- Near-linear Time Approximation Schemes for Clustering in Doubling Metrics. Journal of the ACM, 68(6), 1-34.
- A note on the approximability of deepest-descent circuit steps. Operations Research Letters, 49(3), 310-315.
- Parameterized Approximation Algorithms for Bidirected Steiner Network Problems. ACM Transactions on Algorithms, 17(2), 1-68.
- Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices. SIAM Journal on Discrete Mathematics, 35(1), 546-574.
- Travelling on Graphs with Small Highway Dimension. Algorithmica, 83(5), 1352-1370.
- Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions). SIAM Journal on Computing, 49(2), 318-364.
- The Parameterized Hardness of the k-Center Problem in Transportation Networks. Algorithmica, 82(7), 1989-2005.
- A Tight Lower Bound for Planar Steiner Orientation. Algorithmica, 81(8), 3200-3216.
- Fixed-Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs. Algorithmica, 81(3), 1031-1052.
- A $(1+varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs. SIAM Journal on Computing, 47(4), 1667-1704.
- On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree. Mathematical Programming, 160(1-2), 379-406.
- Lehman's Theorem and the Directed Steiner Tree Problem. SIAM Journal on Discrete Mathematics, 30(1), 141-153.
- Improving the
- An $$O(n^4)$$ O ( n 4 ) Time Algorithm to Compute the Bisection Width of Solid Grid Graphs. Algorithmica, 71(1), 181-200.
- On the Parameterized Complexity of Computing Balanced Partitions in Graphs. Theory of Computing Systems, 57(1), 1-35.
- Balanced Partitions of Trees and Applications. Algorithmica, 71(2), 354-376.
- Fast balanced partitioning is hard even on grids and trees. Theoretical Computer Science, 485, 61-68.
- Computing approximate Nash equilibria in network congestion games. Networks, 59(4), 380-386.
- The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems. ACM Transactions on Computation Theory.
- A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms. Algorithms, 13(6), 146-146.
Chapters
- The Parameterized Complexity of the Survivable Network Design Problem, Symposium on Simplicity in Algorithms (SOSA) (pp. 37-56). Society for Industrial and Applied Mathematics
- A $$(1+{varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs, Automata, Languages, and Programming (pp. 469-480). Springer Berlin Heidelberg
- An $mathcal{O}(n^4)$ Time Algorithm to Compute the Bisection Width of Solid Grid Graphs, Algorithms – ESA 2011 (pp. 143-154). Springer Berlin Heidelberg
- An Time Algorithm to Compute the Bisection Width of Solid Grid Graphs, Algorithms – ESA 2011 (pp. 143-154). Springer Nature
Conference proceedings papers
- Approximation Algorithms and Lower Bounds for Graph Burning. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 275
- On Sparse Hitting Sets: From Fair Vertex Cover to Highway Dimension. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 249
- Generalized $$k$$-Center: Distinguishing Doubling and Highway Dimension (pp 215-229)
- On extended formulations for parameterized steiner trees. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 214
- Efficient fully dynamic elimination forests with applications to detecting long paths and cycles (pp 796-809)
- Fixed-parameter tractability of the weighted edge clique partition problem. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 180
- Parameterized Inapproximability of Independent Set in H-Free Graphs (pp 40-53)
- Polynomial time approximation schemes for clustering in low highway dimension graphs. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 173
- Recoloring interval graphs with limited recourse budget. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 162
- FPT inapproximability of directed cut and connectivity problems. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 148
- Near-Linear Time Approximations Schemes for Clustering in Doubling Metrics. 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), 9 November 2019 - 12 November 2019.
- Travelling on Graphs with Small Highway Dimension (pp 175-189)
- Parameterized approximation algorithms for bidirected steiner network problems. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 112
- The parameterized hardness of the k-center problem in transportation networks. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 101 (pp 191-1913)
- A Tight Lower Bound for Steiner Orientation (pp 65-77)
- Parameterized approximation schemes for steiner trees with small number of Steiner vertices. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 96
- Fast approximation algorithms for the generalized survivable network design problem. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 64 (pp 33.1-33.12)
- The complexity landscape of fixed-parameter directed steiner network problems. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 55
- A (1 + ε)-embedding of low highway dimension graphs into bounded treewidth graphs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 9134 (pp 469-480)
- Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs (pp 588-600)
- On the equivalence of the bidirected and hypergraphic relaxations for steiner tree. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 28 (pp 176-191)
- Improving the H k -Bound on the Price of Stability in Undirected Shapley Network Design Games (pp 158-169)
- Corner cuts are close to optimal: From solid grids to polygons and back. Discrete Applied Mathematics, Vol. 161(7-8) (pp 970-998)
- On the Parameterized Complexity of Computing Graph Bisections (pp 76-87)
- Balanced partitions of trees and applications. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 14 (pp 100-111)
- Fast Balanced Partitioning Is Hard Even on Grids and Trees (pp 372-382)
- Restricted Cuts for Bisections in Solid Grids: A Proof via Polygons (pp 143-154)
- An O4 time algorithm to compute the bisection width of solid grid graphs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 6942 LNCS (pp 143-154)
- An O(n(4)) Time Algorithm to Compute the Bisection Width of Solid Grid Graphs. ALGORITHMS - ESA 2011, Vol. 6942 (pp 143-154)
- Simple Cuts Are Fast and Good: Optimum Right-Angled Cuts in Solid Grids (pp 11-20)
- Computing Approximate Nash Equilibria in Network Congestion Games (pp 209-220)
Preprints
- A $(5/3+{epsilon})$-Approximation for Tricolored Non-crossing Euclidean TSP, arXiv.
- A $(5/3+ε)$-Approximation for Tricolored Non-crossing Euclidean
TSP.
- Parameterized Algorithms for Steiner Forest in Bounded Width Graphs, arXiv.
- Generalized $k$-Center: Distinguishing Doubling and Highway Dimension, arXiv.
- On Sparse Hitting Sets: from Fair Vertex Cover to Highway Dimension, arXiv.
- The Parameterized Complexity of the Survivable Network Design Problem, arXiv.
- A Note on the Approximability of Deepest-Descent Circuit Steps, arXiv.
- Polynomial Time Approximation Schemes for Clustering in Low Highway Dimension Graphs, arXiv.
- Parameterized Inapproximability of Independent Set in $H$-Free Graphs, arXiv.
- A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms, arXiv.
- Efficient fully dynamic elimination forests with applications to detecting long paths and cycles, arXiv.
- Fixed-Parameter Tractability of the Weighted Edge Clique Partition Problem, arXiv.
- Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions), arXiv.
- FPT Inapproximability of Directed Cut and Connectivity Problems, arXiv.
- Travelling on Graphs with Small Highway Dimension, arXiv.
- Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics, arXiv.
- The Parameterized Hardness of the k-Center Problem in Transportation Networks, arXiv.
- Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices, arXiv.
- The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems, arXiv.
- Parameterized Approximation Algorithms for Bidirected Steiner Network Problems, arXiv.
- Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs, arXiv.
- Fast Approximation Algorithms for the Generalized Survivable Network Design Problem, arXiv.
- A $(1 + {varepsilon})$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs, arXiv.
- On the Parameterized Complexity of Computing Balanced Partitions in Graphs, arXiv.
- Improving the H_k-Bound on the Price of Stability in Undirected Shapley Network Design Games, arXiv.
- Fast Balanced Partitioning is Hard, Even on Grids and Trees, arXiv.
- Parameterized Inapproximability of Independent Set in H-Free Graphs. Algorithmica, 85(4), 902-928.
- Research group
-
Foundations of Computation research group