Publications

Conference papers:

2023:

• Matej Lieskovský, Jiří Sgall, Andreas Emil Feldmann: Approximation Algorithms and Lower Bounds for Graph Burning. In Proceedings of the 26th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX).

2022:

• Yann Disser, Johannes Blum, Andreas Emil Feldmann, Siddharth Gupta, Anna Zych-Pawlewicz: On Sparse Hitting Sets: from Fair Vertex Cover to Highway Dimension. In Proceedings of the 17th International Symposium on Parameterized and Exact Computation (IPEC).

• Andreas Emil Feldmann, Tung Anh Vu: Generalized k-Center: Distinguishing Doubling and Highway Dimension. In Proceedings of the 48th International Workshop on Graph-Theoretic Concepts in Computer Science (WG).

• Andreas Emil Feldmann, Anish Mukherjee, Erik Jan van Leeuwen: The Parameterized Complexity of the Survivable Network Design Problem. In Proceedings of the Symposium on Simplicity in Algorithms (SOSA).

2021:

• Andreas Emil Feldmann, Ashutosh Rai: On Extended Formulations for Parameterized Steiner Trees. In Proceedings of the 16th International Symposium on Parameterized and Exact Computation (IPEC).

• Jiehua Chen, Wojciech Czerwiński, Yann Disser, Andreas Emil Feldmann, Danny Hermelin, Wojciech Nadara, Marcin Pilipczuk, Michał Pilipczuk, Manuel Sorge, Bartłomiej Wróblewski, Anna Zych-Pawlewicz: Efficient fully dynamic elimination forests with applications to detecting long paths and cycles. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA).

2020:

• Davis Issac, Andreas Emil Feldmann, Ashutosh Rai: Fixed-Parameter Tractability of the Weighted Edge Clique Partition Problem. In Proceedings of the 15th International Symposium on Parameterized and Exact Computation (IPEC).

• Andreas Emil Feldmann, David Saulpic: Polynomial Time Approximation Schemes for Clustering in Low Highway Dimension Graphs. In Proceedings of the 28th Annual European Symposium on Algorithms (ESA).

• Pavel Dvořák, Andreas Emil Feldmann, Ashutosh Rai, Paweł Rzążewski: Parameterized Inapproximability of Independent Sets in H-Free Graphs. In Proceedings of the 46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG).

• Bartłomiej Bosek, Yann Disser, Andreas Emil Feldmann, Jakub Pawlewicz, Anna Zych-Pawlewicz: Recoloring Interval Graphs with Limited Recourse Budget. In Proceedings of the 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT).

2019:

• Rajesh Chitnis, Andreas Emil Feldmann: FPT Inapproximability of Directed Cut and Connectivity Problems. In Proceedings of the 14th International Symposium on Parameterized and Exact Computation (IPEC).

• Vincent Cohen-Addad, Andreas Emil Feldmann, David Saulpic: Near-Linear-Time Approximation Schemes for Clustering in Doubling Metrics. In Proceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS).

• Yann Disser, Andreas Emil Feldmann, Max Klimm, Jochen Könemann: Travelling on Graphs with Small Highway Dimension. In Proceedings of the 45th International Workshop on Graph-Theoretic Concepts in Computer Science (WG). [presentation]

2018:

• Rajesh Chitnis, Andreas Emil Feldmann, Pasin Manurangsi: Parameterized Approximation Algorithms for Bidirected Steiner Network Problems. In Proceedings of the 26th Annual European Symposium on Algorithms (ESA). [presentation]

• Andreas Emil Feldmann, Dániel Marx: The Parameterized Hardness of the k-Center Problem in Transportation Networks. In Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT). [presentation]

• Rajesh Chitnis, Andreas Emil Feldmann: A Tight Lower Bound for Steiner Orientation. In Proceedings of the 13th International Computer Science Symposium in Russia (CSR).

• Pavel Dvořák, Andreas Emil Feldmann, Dušan Knop, Tomáš Masařík, Tomáš Toufar, Pavel Veselý: Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices. In Proceedings of the 35th International Symposium on Theoretical Aspects of Computer Science (STACS). [presentation][implementation by Tamás Kemény]

2016:

• Andreas Emil Feldmann, Jochen Könemann, Kanstantsin Pashkovich, Laura Sanità: Fast Approximation Algorithms for the Generalized Survivable Network Design Problem. In Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC).

• Andreas Emil Feldmann, Dániel Marx: The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP). [presentation]

2015:

• Andreas Emil Feldmann: Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP). [presentation]

• Andreas Emil Feldmann, Wai Shing Fung, Jochen Könemann, Ian Post: A (1 + ε)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP). [presentation]

2014:

• Andreas Emil Feldmann, Jochen Könemann, Neil Olver, Laura Sanita: On the Equivalence of the Bidirected and Hypergraphic Relaxations for Steiner Tree. In Proceedings of the 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX).

2013:

• Rene van Bevern, Andreas Emil Feldmann, Manuel Sorge, Ondřej Suchý: On the Parameterized Complexity of Graph Bisections. In Proceedings of the 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG).

• Yann Disser, Andreas Emil Feldmann, Max Klimm, Matus Mihalak: Improving the H_k-Bound on the Price of Stability in Undirected Shapley Network Design Games. In Proceedings of the 8th International Conference on Algorithms and Complexity (CIAC).

2012:

• Andreas Emil Feldmann: Fast Balanced Partitioning is Hard, even on Grids and Trees. In Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science (MFCS). [presentation]

• Andreas Emil Feldmann, Luca Foschini: Balanced Partitions of Trees and Applications. In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS). [presentation]

2011:

• Andreas Emil Feldmann, Shantanu Das, Peter Widmayer: Restricted Cuts for Bisections in Solid Grids: A Proof via Polygons. In Proceedings of the 37th International Workshop on Graph-Theoretic Concepts in Computer Science (WG). [presentation]

• Andreas Emil Feldmann, Peter Widmayer: An O(n^4) Time Algorithm to Compute the Bisection Width of Solid Grid Graphs. In Proceedings of the 19th Annual European Symposium on Algorithms (ESA). [presentation]

2010:

• Andreas Emil Feldmann, Shantanu Das, Peter Widmayer: Simple Cuts are Fast and Good: Optimum Right-Angled Cuts in Solid Grids. In Proceedings of the 4th Annual International Conference on Combinatorial Optimization and Applications (COCOA). [presentation]

2008:

• Andreas Emil Feldmann, Heiko Röglin, Berthold Vöcking: Computing Approximate Nash Equilibria in Network Congestion Games. In Proceedings of the 15th International Colloquium on Structural Information and Communication Complexity (SIROCCO).

Journal publications (by year of acceptance):

2023:

• Andreas Emil Feldmann, Anish Mukherjee, Erik Jan van Leeuwen: The Parameterized Complexity of the Survivable Network Design Problem. Journal of Computer and System Sciences.

2022:

• Andreas Emil Feldmann, Dániel Marx: The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems. Transactions on Computation Theory.

• Pavel Dvořák, Andreas Emil Feldmann, Ashutosh Rai, Paweł Rzążewski: Parameterized Inapproximability of Independent Sets in H-Free Graphs. Algorithmica.

2021:

•  Vincent Cohen-Addad, Andreas Emil Feldmann, David Saulpic: Near-Linear-Time Approximation Schemes for Clustering in Doubling Metrics. Journal of the ACM.

• Andreas Emil Feldmann, David Saulpic: Polynomial Time Approximation Schemes for Clustering in Low Highway Dimension Graphs. Journal of Computer and System Sciences [Special issue of JCSS devoted to the best papers of ESA2020].

• Rajesh Chitnis, Andreas Emil Feldmann, Pasin Manurangsi: Parameterized Approximation Algorithms for Bidirected Steiner Network Problems. Transactions on Algorithms.

• Steffen Borgwardt, Cornelius Brand, Andreas Emil Feldmann, Martin Koutecký: A Note on the Approximability of Deepest-Descent Circuit Steps. Operations Research Letters.

2020:

• Pavel Dvořák, Andreas Emil Feldmann, Dušan Knop, Tomáš Masařík, Tomáš Toufar, Pavel Veselý: Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices. SIAM Journal on Discrete Mathematics.

• Yann Disser, Andreas Emil Feldmann, Max Klimm, Jochen Könemann: Travelling on Graphs with Small Highway Dimension. Algorithmica.

• Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi: A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms. Algorithms [Special Issue "New Frontiers in Parameterized Complexity and Algorithms"].

2019:

• Rajesh Chitnis, Andreas Emil Feldmann, MohammadTaghi Hajiaghayi, Dániel Marx: Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions). SIAM Journal on Computing.

• Andreas Emil Feldmann, Dániel Marx: The Parameterized Hardness of the k-Center Problem in Transportation Networks. Algorithmica.

2018:

• Rajesh Chitnis, Andreas Emil Feldmann, Ondřej Suchý: A Tight Lower Bound for Planar Steiner Orientation. Algorithmica.

2017:

• Andreas Emil Feldmann: Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs. Algorithmica.

• Andreas Emil Feldmann, Wai Shing Fung, Jochen Könemann, Ian Post: A (1 + ε)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs. SIAM Journal on Computing.

2016:

• Andreas Emil Feldmann, Jochen Könemann, Neil Olver, Laura Sanita: On the Equivalence of the Bidirected and Hypergraphic Relaxations for Steiner Tree. Mathematical Programming.

2015:

• Ahmad Abdi, Andreas Emil Feldmann, Bertrand Guenin, Jochen Könemann, Laura Sanità: Lehman’s Theorem and the Directed Steiner Tree Problem. SIAM Journal on Discrete Mathematics.

2014:

• Yann Disser, Andreas Emil Feldmann, Max Klimm, Matus Mihalak: Improving the H_k-Bound on the Price of Stability in Undirected Shapley Network Design Games. Theoretical Computer Science.

• Andreas Emil Feldmann, Peter Widmayer: An O(n^4) Time Algorithm to Compute the Bisection Width of Solid Grid Graphs. Algorithmica.

• Rene van Bevern, Andreas Emil Feldmann, Manuel Sorge, Ondřej Suchý: On the Parameterized Complexity of Computing Balanced Partitions in Graphs. Theory of Computing Systems.

2013:

• Andreas Emil Feldmann, Luca Foschini: Balanced Partitions of Trees and Applications. Algorithmica.

• Andreas Emil Feldmann, Shantanu Das, Peter Widmayer: Corner Cuts are Close to Optimal: From Solid Grids to Polygons and Back. Discrete Applied Mathematics.

• Andreas Emil Feldmann: Fast Balanced Partitioning is Hard, even on Grids and Trees. Theoretical Computer Science.

2012:

• Andreas Emil Feldmann, Heiko Röglin, Berthold Vöcking: Computing Approximate Nash Equilibria in Network Congestion Games. Networks.