Meike Neuwohner

Meike Neuwohner

orcid

Research Focus & Metrics

Academic Career Length

5Years (2022-Present)

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

Representative Publications

View All Publications

28 October 2023 in Mathematical Programming
Verified
Journal Article
Open access
PDF file
MNMeike Neuwohner
Meike Neuwohner
We consider the weighted k-set packing problem, where, given a collection $${\mathcal {S}}$$ S of sets, each of cardinality at most k, and a positive weight function $$w:{\mathcal {S}}\rightarrow {\mathbb {Q}}_{>0}$$ w : S → Q > 0 , the task is to find a sub-collection of $${\mathcal {S}}$$ S consisting of pairwise disjoint sets of maximum total weight. As this problem does not permit a polynomial-time $$o(\frac{k}{\log k})$$ o ( k log k ) -approximation unless $$P=NP$$ P = N P (Hazan et al. in Comput Complex 15:20–39, 2006. https://doi.org/10.1007/s00037-006-0205-6), most previous approaches rely on local search. For twenty years, Berman’s algorithm SquareImp (Berman, in: Scandinavian workshop on algorithm theory, Springer, 2000. https://doi.org/10.1007/3-540-44985-X_19), which yields a polynomial-time $$\frac{k+1}{2}+\epsilon $$ k + 1 2 + ϵ -approximation for any fixed $$\epsilon >0$$ ϵ > 0 , has remained unchallenged. Only recently, it could be improved to $$\frac{k+1}{2}-\frac{1}{63,700,993}$$ k + 1 2 - 1 63 , 700 , 993 by Neuwohner (38th International symposium on theoretical aspects of computer science (STACS 2021), Leibniz international proceedings in informatics (LIPIcs), 2021. https://doi.org/10.4230/LIPIcs.STACS.2021.53). In her paper, she showed that instances for which the analysis of SquareImp is almost tight are “close to unweighted” in a certain sense. But for the unit weight variant, the best known approximation guarantee is $$\frac{k+1}{3}+\epsilon $$ k + 1 3 + ϵ (Fürer and Yu in International symposium on combinatorial optimization, Springer, 2014. https://doi.org/10.1007/978-3-319-09174-7_35). Using this observation as a starting point, we conduct a more in-depth analysis of close-to-tight instances of SquareImp. This finally allows us to generalize techniques used in the unweighted case to the weighted setting. In doing so, we obtain approximation guarantees of $$\frac{k+\epsilon _k}{2}$$ k + ϵ k 2 , where $$\lim _{k\rightarrow \infty } \epsilon _k = 0$$ lim k → ∞ ϵ k = 0 . On the other hand, we prove that this is asymptotically best possible in that local improvements of logarithmically bounded size cannot produce an approximation ratio below $$\frac{k}{2}$$ k 2 .

16 June 2025 in ACM Transactions on Economics and Computation
Verified
Journal Article
Open access
KEKatharina Eickhoff
Katharina Eickhoff
MNMeike Neuwohner
Meike Neuwohner
BPBritta Peis
Britta Peis
NRNiklas Rieken
Niklas Rieken
LKLaura Vargas Koch
Laura Vargas Koch
LVLászló A. Végh
László A. Végh
We consider dynamic auctions for finding Walrasian equilibria in markets with indivisible items and strong gross substitutes valuation functions. Each price adjustment step in these auction algorithms requires finding an inclusion-wise minimal maximally overdemanded set or an inclusion-wise minimal maximally underdemanded set at the current prices. Both can be formulated as a submodular function minimization problem. We observe that minimizing this submodular function corresponds to a polymatroid sum problem, and using this viewpoint, we give a fast and simple push-relabel algorithm for finding the required sets. This improves on the previously best running time of Murota, Shioura and Yang (ISAAC 2013). Our algorithm is an adaptation of the push-relabel framework by Frank and Miklós (JJIAM 2012) to the particular setting. We obtain a further improvement for the special case of unit-supplies. We further show the following monotonicity properties of Walrasian prices: both the minimal and maximal Walrasian prices can only increase if supply of goods decreases, or if the demand of buyers increases. This is derived from a fine-grained analysis of market prices. We call packing prices a price vector such that there is a feasible allocation where each buyer obtains a utility maximizing set. Conversely, by covering prices we mean a price vector such that there exists a collection of utility maximizing sets of the buyers that include all available goods. We show that for strong gross substitutes valuations, the component-wise minimal packing prices coincide with the minimal Walrasian prices and the component-wise maximal covering prices coincide with the maximal Walrasian prices. These properties in turn lead to the price monotonicity results.

8 September 2023 in ACM Transactions on Design Automation of Electronic Systems
Verified
Journal Article
Open access
SHStefan Hougardy
Stefan Hougardy
MNMeike Neuwohner
Meike Neuwohner
USUlrike Schorr
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 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 article, we show how to optimize squared 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 𝒪( n · log ( n )), where n denotes the number of cells involved. Opposed to prior works, we do not artificially bound the maximum cell movement and can guarantee to find an optimum solution. Our approach also allows us to include gridding and movebound constraints for the cells. Experimental results show an average percental decrease of over 26% in the total squared movement when compared to a legalization approach that fixes cells of more than single-row height after Global Placement.

8 July 2025 in Operations Research Letters
Verified
Journal Article
Closed access
AAAhmad Abdi
Ahmad Abdi
MDMahsa Dalirrooyfard
Mahsa Dalirrooyfard
MNMeike Neuwohner
Meike Neuwohner