1 citations · 4 across the 13 of their papers we have counts for
16 papers
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…
Boxicity and Threshold Dimension of Zero Divisor Graphs
Marco Caoduro, Meike Neuwohner
The zero divisor graph of a finite commutative ring has as vertices the non-zero zero divisors of , with an edge between two elements exactly when their product is ze…
Cosigning Crossing Families and Outer-Planar Gadgets
Ahmad Abdi, Mahsa Dalirrooyfard, Meike Neuwohner
Let be a crossing family over ground set , that is, for any two sets with nonempty intersection and proper union, both sets are in . Let $…
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…
Strong orientation of a connected graph for a crossing family
Ahmad Abdi, Mahsa Dalirrooyfard, Meike Neuwohner
Given a connected graph and a crossing family over ground set such that for every , we prove there exists a strong or…
Characterizing unimodular laminar hypergraphs via forbidden subhypergraphs
Marco Caoduro, Meike Neuwohner, Joseph Paat
The incidence matrix of a graph is totally unimodular if and only if the graph is bipartite, i.e., it contains no odd cycles. We extend the characterization of total unimodularity…
Faster Dynamic Auctions via Polymatroid Sum
Katharina Eickhoff, Meike Neuwohner, Britta Peis +3
We consider dynamic auctions for finding Walrasian equilibria in markets with indivisible items and strong gross substitutes valuation functions. Each price adjustment step in thes…
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…
The Pareto cover problem
Bento Natura, Meike Neuwohner, Stefan Weltge
We introduce the problem of finding a set of points in such that the expected cost of the cheapest point in that dominates a random point from is mi…
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…
Reducing Moser's Square Packing Problem to a Bounded Number of Squares
Meike Neuwohner
The problem widely known as Moser's Square Packing Problem asks for the smallest area such that for any set of squares of total area , there exists a rectangle of ar…
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…