Zobrazeno 1 - 10
of 23
pro vyhledávání: '"Neuwohner, Meike"'
Given a connected graph $G=(V,E)$ and a crossing family $\mathcal{C}$ over ground set $V$ such that $|\delta_G(U)|\geq 2$ for every $U\in \mathcal{C}$, we prove there exists a strong orientation of $G$ for $\mathcal{C}$, i.e., an orientation of $G$ s
Externí odkaz:
http://arxiv.org/abs/2411.13202
Grossman et al. show that the subdeterminants of the incidence matrix of a graph can be characterized using the graph's odd cycle packing number. In particular, a graph's incidence matrix is totally unimodular if and only if the graph is bipartite. W
Externí odkaz:
http://arxiv.org/abs/2411.10593
Autor:
Neuwohner, Meike
The Maximum Leaf Spanning Arborescence problem (MLSA) is defined as follows: Given a directed graph $G$ and a vertex $r\in V(G)$ from which every other vertex is reachable, find a spanning arborescence rooted at $r$ maximizing the number of leaves (v
Externí odkaz:
http://arxiv.org/abs/2407.04342
Autor:
Eickhoff, Katharina, Neuwohner, Meike, Peis, Britta, Rieken, Niklas, Koch, Laura Vargas, Végh, László A.
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 maxima
Externí odkaz:
http://arxiv.org/abs/2310.08454
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 $(V,c)$ and an activation probability $p(v)$ for each customer $v\in V$
Externí odkaz:
http://arxiv.org/abs/2309.10663
Autor:
Neuwohner, Meike
The weighted $3$-Set Packing problem is defined as follows: As input, we are given a collection $\mathcal{S}$ of sets, each of cardinality at most $3$ and equipped with a positive weight. The task is to find a disjoint sub-collection of maximum total
Externí odkaz:
http://arxiv.org/abs/2305.07808
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
Externí odkaz:
http://arxiv.org/abs/2202.08035
Autor:
Neuwohner, Meike
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\su
Externí odkaz:
http://arxiv.org/abs/2202.01248
Autor:
Neuwohner, Meike1 (AUTHOR) neuwohner@or.uni-bonn.de
Publikováno v:
Mathematical Programming. Jul2024, Vol. 206 Issue 1/2, p389-427. 39p.
Autor:
Neuwohner, Meike
We consider the Maximum Weight Independent Set Problem (MWIS) in $d$-claw free graphs, i.e. the task of computing an independent set of maximum weight in a given $d$-claw free graph $G=(V,E)$ equipped with a positive weight function $w:V\rightarrow\m
Externí odkaz:
http://arxiv.org/abs/2106.03555