Andreas Emil Feldmann

Dr. Andreas Emil Feldmann

orcid

Research Focus & Metrics

Academic Career Length

19Years (2008-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
19 June 2020 in Algorithms
Verified
Journal Article
Open access
PDF file
AFAndreas Emil Feldmann
Andreas Emil Feldmann
KSKarthik C. S.
Karthik C. S.
ELEuiwoong Lee
Euiwoong Lee
PMPasin Manurangsi
Pasin Manurangsi
Parameterization and approximation are two popular ways of coping with NP-hard problems. More recently, the two have also been combined to derive many interesting results. We survey developments in the area both from the algorithmic and hardness perspectives, with emphasis on new techniques and potential future research directions.

10 July 2013 in Algorithmica
Verified
Journal Article
Open access
PDF file
AFAndreas Emil Feldmann
Andreas Emil Feldmann
LFLuca Foschini
Luca Foschini
We study the problem of finding the minimum number of edges that, when cut, form a partition of the vertices into k sets of equal size. This is called the k-BALANCED PARTITIONING problem. The problem is known to be inapproximable within any finite factor on general graphs, while little is known about restricted graph classes. We show that the k-BALANCED PARTITIONING problem remains APX-hard even when restricted to unweighted tree instances with constant maximum degree. If instead the diameter of the tree is constant we prove that the problem is NP-hard to approximate within n c, for any constant c<1. If vertex sets are allowed to deviate from being equal-sized by a factor of at most 1+ε, we show that solutions can be computed on weighted trees with cut cost no worse than the minimum attainable when requiring equal-sized sets. This result is then extended to general graphs via decompositions into trees and improves the previously best approximation ratio from O(log1.5(n)/ε 2) [Andreev and Räcke in Theory Comput. Syst. 39(6):929–939, 2006] to O(logn). This also settles the open problem of whether an algorithm exists for which the number of edges cut is independent of ε.

31 October 2021 in Journal of the ACM
Verified
Journal Article
Open access
VCVincent Cohen-Addad
Vincent Cohen-Addad
AFAndreas Emil Feldmann
Andreas Emil Feldmann
DSDavid Saulpic
David Saulpic
We consider the classic Facility Location, k -Median, and k -Means problems in metric spaces of doubling dimension d . We give nearly linear-time approximation schemes for each problem. The complexity of our algorithms is Õ(2 (1/ε) O(d2) n) , making a significant improvement over the state-of-the-art algorithms that run in time n (d/ε) O(d) . Moreover, we show how to extend the techniques used to get the first efficient approximation schemes for the problems of prize-collecting k -Median and k -Means and efficient bicriteria approximation schemes for k -Median with outliers, k -Means with outliers and k -Center.

1 May 2013 in Theoretical Computer Science
Verified
Journal Article
Closed access
AFAndreas Emil Feldmann
Andreas Emil Feldmann

18 February 2016 in Mathematical Programming
Verified
Journal Article
Open access
PDF file
AFAndreas Emil Feldmann
Andreas Emil Feldmann
JKJochen Könemann
Jochen Könemann
NONeil Olver
Neil Olver
LSLaura Sanità
Laura Sanità
The bottleneck of the currently best \((\ln (4)+{\varepsilon })\)-approximation algorithm for the NP-hard Steiner tree problem is the solution of its large, so called hypergraphic, linear programming relaxation (HYP). Hypergraphic LPs are strongly NP-hard to solve exactly, and it is a formidable computational task to even approximate them sufficiently well. We focus on another well-studied but poorly understood LP relaxation of the problem: the bidirected cut relaxation (BCR). This LP is compact, and can therefore be solved efficiently. Its integrality gap is known to be greater than 1.16, and while this is widely conjectured to be close to the real answer, only a (trivial) upper bound of 2 is known. In this article, we give an efficient constructive proof that BCR and HYP are polyhedrally equivalent in instances that do not have an (edge-induced) claw on Steiner vertices, i.e., they do not contain a Steiner vertex with three Steiner neighbours. This implies faster \(\ln (4)\)-approximations for these graphs, and is a significant step forward from the previously known equivalence for (so called quasi-bipartite) instances in which Steiner vertices form an independent set. We complement our results by showing that even restricting to instances where Steiner vertices induce one single star, determining whether the two relaxations are equivalent is NP-hard.

3 February 2020 in Algorithmica
Verified
Journal Article
Open access
PDF file
AFAndreas Emil Feldmann
Andreas Emil Feldmann
DMDániel Marx
Dániel Marx
In this paper we study the hardness of the \(k\)-Center problem on inputs that model transportation networks. For the problem, a graph \(G=(V,E)\) with edge lengths and an integer k are given and a center set \(C\subseteq V\) needs to be chosen such that \(|C|\le k\). The aim is to minimize the maximum distance of any vertex in the graph to the closest center. This problem arises in many applications of logistics, and thus it is natural to consider inputs that model transportation networks. Such inputs are often assumed to be planar graphs, low doubling metrics, or bounded highway dimension graphs. For each of these models, parameterized approximation algorithms have been shown to exist. We complement these results by proving that the \(k\)-Center problem is W[1]-hard on planar graphs of constant doubling dimension, where the parameter is the combination of the number of centers k, the highway dimension h, and the pathwidth p. Moreover, under the exponential time hypothesis there is no \(f(k,p,h)\cdot n^{o(p+\sqrt{k+h})}\) time algorithm for any computable function f. Thus it is unlikely that the optimum solution to \(k\)-Center can be found efficiently, even when assuming that the input graph abides to all of the above models for transportation networks at once! Additionally we give a simple parameterized \((1+{\varepsilon })\)-approximation algorithm for inputs of doubling dimension d with runtime \((k^k/{\varepsilon }^{O(kd)})\cdot n^{O(1)}\). This generalizes a previous result, which considered inputs in D-dimensional \(L_q\) metrics.