Source author record

Meike Neuwohner

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Geometry Discrete Mathematics math.OC

Catalog footprint

Research overview

3works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Passing the Limits of Pure Local Search for Weighted $k$ -Set Packing

We study the weighted $k$ -Set Packing problem: Given a collection $S$ of sets, each of cardinality at most $k$ , together with a positive weight function $w:\mathcal{S}\rightarrow\mathbb{Q}_{>0}$ , the task is to compute a disjoint sub-collection $A\subseteq \mathcal{S}$ of maximum total weight. For $k\leq 2$ , the weighted $k$ -Set Packing problem can be solved in polynomial time, but for $k\geq 3$ , it becomes $NP$ -hard. Recently, Neuwohner has shown how to obtain approximation guarantees of $\frac{k+ε_k}{2}$ with $\lim_{k\rightarrow\infty}ε_k=0$ . She further showed her result to be asymptotically best possible in that no algorithm considering local improvements of logarithmically bounded size with respect to some fixed power of the weight function can yield an approximation guarantee better than $\frac{k}{2}$ . In this paper, we finally show how to beat the threshold of $\frac{k}{2}$ for the weighted $k$ -Set Packing problem by $Ω(k)$ . We achieve this by combining local search with the application of a black box algorithm for the unweighted $k$ -Set Packing problem to carefully chosen sub-instances. In doing so, we manage to link the approximation ratio for general weights to the one achievable in the unweighted case and we obtain guarantees of at most $\frac{k+1}{2}-2\cdot 10^{-4}$ for all $k\geq 4$ .

preprint2022arXiv

The Pareto cover problem

We introduce the problem of finding a set $B$ of $k$ points in $[0,1]^n$ such that the expected cost of the cheapest point in $B$ that dominates a random point from $[0,1]^n$ is minimized. We study the case where the coordinates of the random points are independently distributed and the cost function is linear. This problem arises naturally in various application areas where customers' requests are satisfied based on predefined products, each corresponding to a subset of features. We show that the problem is NP-hard already for $k=2$ when each coordinate is drawn from $\{0,1\}$ , and obtain an FPTAS for general fixed $k$ under mild assumptions on the distributions.

preprint2021arXiv

A Fast Optimal Double Row Legalization Algorithm

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 independently. However, this is no longer true for recent technologies, where a substantial number of cells of double- or even arbitrary multiple-row height is to be expected. Due to interdependencies between the cell placements within several rows, the legalization task becomes considerably harder. In this paper, we show how to optimize quadratic cell movement for pairs of adjacent rows comprising cells of single- as well as double-row height with a fixed left-to-right ordering in time $\mathcal{O}(n\cdot\log(n))$ , whereby $n$ denotes the number of cells involved. Opposed to prior works, we thereby do not artificially bound the maximum cell movement and can guarantee to find an optimum solution. Experimental results show an average percental decrease of over $26\%$ in the total quadratic movement when compared to a legalization approach that fixes cells of more than single-row height after Global Placement.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Meike Neuwohner

Research overview

Is this your work?

3 publications

Passing the Limits of Pure Local Search for Weighted $k$ -Set Packing

The Pareto cover problem

A Fast Optimal Double Row Legalization Algorithm

See the researcher in context

Building this map preview

Meike Neuwohner

Research overview

Is this your work?

3 publications

Passing the Limits of Pure Local Search for Weighted kkk-Set Packing

The Pareto cover problem

A Fast Optimal Double Row Legalization Algorithm

See the researcher in context

Building this map preview

Passing the Limits of Pure Local Search for Weighted $k$ -Set Packing