1 citations · 4 across the 13 of their papers we have counts for
9 papers · 1 filter
Settling the Approximability of Submodular Facility Location
Adam N. Elmachtoub, Bento Natura, Meike Neuwohner
In submodular facility location (SFL), introduced by Svitkina and Tardos (SODA 2006), clients in a metric space are assigned to facilities . A facility serving a s…
Approximation Schemes for Planar Graph Connectivity Problems
Meike Neuwohner, Vera Traub, Rico Zenklusen
Finding a smallest subgraph that is k-edge-connected, or augmenting a k-edge-connected graph with a smallest subset of given candidate edges to become (k+1)-edge-connected, are amo…
A Better-Than-2 Approximation for the Directed Tree Augmentation Problem
Meike Neuwohner, Olha Silina, Michael Zlatin
We introduce and study a directed analogue of the weighted Tree Augmentation Problem (WTAP). In the weighted Directed Tree Augmentation Problem (WDTAP), we are given an oriented tr…
Improved guarantees for the a priori TSP
Jannis Blauth, Meike Neuwohner, Luise Puhlmann +1
We revisit the a priori TSP (with independent activation) and prove stronger approximation guarantees than were previously known. In the a priori TSP, we are given a metric space $…
The --Set Packing problem and a -approximation for the Maximum Leaf Spanning Arborescence problem in rooted dags
Meike Neuwohner
The weighted -Set Packing problem is defined as follows: As input, we are given a collection of sets, each of cardinality at most and equipped with a positive…
Passing the Limits of Pure Local Search for Weighted -Set Packing
Meike Neuwohner
We study the weighted -Set Packing problem: Given a collection of sets, each of cardinality at most , together with a positive weight function $w:\mathcal{S}\rightarrow\m…
The Limits of Local Search for the Maximum Weight Independent Set Problem in d-Claw Free Graphs
Meike Neuwohner
We consider the Maximum Weight Independent Set Problem (MWIS) in -claw free graphs, i.e. the task of computing an independent set of maximum weight in a given -claw free grap…
An Improved Approximation Algorithm for the Maximum Weight Independent Set Problem in d-Claw Free Graphs
Meike Neuwohner
In this paper, we consider the task of computing an independent set of maximum weight in a given -claw free graph equipped with a positive weight function $w:V\rightar…
A Fast Optimal Double Row Legalization Algorithm
Stefan Hougardy, Meike Neuwohner, Ulrike Schorr
In Placement Legalization, it is often assumed that (almost) all standard cells possess the same height and can therefore be aligned in cell rows, which can then be treated indepen…