Embedded Files
Are you ...
Are you ...
interested to work on a subject at the frontier of research?
not afraid of topics in theoretical computer science?
fascinated by insights into the nature of computation?
Then do an internship in the new and exciting research area of ...
Parameterized Approximation Algorithms
Parameterized Approximation Algorithms
In many applications we would like to compute solutions to problems, which turn out to be NP-hard (e.g., the Traveling Salesman or Vertex Cover problem). Two standard approaches to handle NP-hard problems are
approximation algorithms, where the runtime should be polynomial in the input size, but the computed solution may deviate from the optimum,
fixed-parameter tractability, where the optimum solution should be computed, but any exponential runtime should be isolated to a “parameter”, which is a value describing some property of the input and is typically small.
What however if we can prove that such algorithms are unlikely to exist? In this case we may still hope to beat these negative results by combining the above two approaches and obtain the novel paradigm of
fixed-parameter approximation algorithms, where the computed solution may deviate from the optimum and the runtime should have exponential dependence only in some given parameter.
Such algorithms have only been considered rather recently, but this new approach has the potential to revolutionise the way algorithms are designed in combinatorial optimisation, and you could be one of the pioneers paving the way!
For an introduction and overview of this new and exciting research area, please have a look at this survey paper:
Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi: A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms. Algorithms, 2020, https://arxiv.org/abs/2006.04411
Some examples of interesting research topics you could work on:
Some examples of interesting research topics you could work on:
The highway dimension of a graph is a parameter that models transportation networks. Can we exploit this parameter to beat the state-of-the-art algorithms for problems that typically occur on transportation networks (e.g., Facility Location or Vehicle Routing problems)?
Some examples of previous results on this topic:
Andreas Emil Feldmann, David Saulpic: Polynomial Time Approximation Schemes for Clustering in Low Highway Dimension Graphs. Journal of Computer and System Sciences, 2021.
https://arxiv.org/abs/2006.12897Andreas 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), 2022.
https://arxiv.org/pdf/2209.00675.pdfAndreas 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, 2017.
https://arxiv.org/abs/1502.04588
In network design we connect clients in a network through some subnetwork with specific properties (e.g., minimizing costs and/or introducing fault tolerance to network failures). Is there a way to bypass known negative results for these well-studied problems using parameterized approximation algorithms?
Some examples of previous results on this topic:
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, 2020.
https://arxiv.org/abs/1710.00668Rajesh Chitnis, Andreas Emil Feldmann, Pasin Manurangsi: Parameterized Approximation Algorithms for Bidirected Steiner Network Problems. Transactions on Algorithms, 2021.
https://arxiv.org/abs/1707.06499
Linear programs (LPs) are a ubiquitous tool to obtain approximation algorithms, but are also used for fixed-parameter algorithms. Can the deep theory behind these powerful tools be harnessed for parameterized approximations as well?
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), 2021.
https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=15401
If you are interested
If you are interested
don’t hesitate to contact Dr. Andreas Emil Feldmann at feldmann.a.e@gmail.com
At the time of writing, a fully funded PhD position is available under my supervision at the University of Sheffield.
Google Sites
Report abuse