Andrea E. F. Clementi, Luca Trevisan

We provide new non-approximability results for the restrictions

of the min-VC problem to bounded-degree, sparse and dense graphs.

We show that for a sufficiently large B, the recent 16/15 lower

bound proved by Bellare et al. extends with negligible

loss to graphs with bounded ...
more >>>

Dorit Dor, Shay Halperin, Uri Zwick

Let G=(V,E) be an unweighted undirected graph on n vertices. A simple

argument shows that computing all distances in G with an additive

one-sided error of at most 1 is as hard as Boolean matrix

multiplication. Building on recent work of Aingworth, Chekuri and

Motwani, we describe an \tilde{O}(min{n^{3/2}m^{1/2},n^{7/3}) time

more >>>

Georgios Stamoulis

Given a weighted graph $G = (V,E,w)$, with weight function $w: E \rightarrow \mathbb{Q^+}$, a \textit{matching} $M$ is a set of pairwise non-adjacent edges. In the optimization setting, one seeks to find a matching of \textit{maximum} weight. In the \textit{multi-criteria} (or \textit{multi-budgeted}) setting, we are also given $\ell$ length functions ... more >>>

Daniel Kane, Shachar Lovett, Sankeerth Rao Karingula

Assume that the edges of the complete bipartite graph $K_{n,n}$ are labeled with elements of $\mathbb{F}_2^d$, such that the sum over

any simple cycle is nonzero. What is the smallest possible value of $d$? This problem was raised by Gopalan et al. [SODA 2017] as it characterizes the alphabet size ...
more >>>