Algorithmica

Finding a minimum vertex cover in a network is a fundamental NP-complete graph problem. One way to deal with its computational hardness, is to trade the qualitative performance of an algorithm (allowing non-optimal outputs) for an improved running ...$\sqrt{\mathrm{}}$$\mathrm{}\mathrm{}$$\mathcal{}$

A k-page upward book embedding (kUBE) of a directed acyclic graph G is a book embeddings of G on k pages with the additional requirement that the vertices appear in a topological ordering along the spine of the book. The kUBE Testing problem, ...$\mathrm{}$$\mathrm{}$$\mathrm{}$${}^{\mathrm{}}$$$$$$\mathrm{}$

We examine the problem of discovering the set P of points in a given topology that constitutes a k-median set for that topology, while maintaining location privacy. That is, there exists a set U of points in a d-dimensional topology for which a k-...

Consider the following problem: You have a device that is supposed to compute a linear combination of its inputs, which are taken from some finite field. However, the device may be faulty and compute arbitrary functions of its inputs. Is it ...

We study the Non-preemptive Peak Demand Minimization (NPDM) problem, where we are given a set of jobs, specified by their processing times and energy requirements. The goal is to schedule all jobs within a fixed time period such that the peak load ...$\mathrm{}\mathrm{}$$\mathrm{}$$\mathrm{}\mathrm{}$$\mathrm{}\mathrm{}$

Over the last two decades, a significant line of work in theoretical algorithms has made progress in solving linear systems of the form $\mathbf{L}\mathbf{x}=\mathbf{b}$, where $\mathbf{L}$ is the Laplacian matrix of a weighted graph with weights $w(i,j)>0$ on the edges. The solution $\mathbf{x}$ of ...${}^{\mathrm{}}$$\mathrm{}$$\stackrel{}{}{}^{\mathrm{}}$${}^{\mathrm{}}$$\mathrm{}$

Multiwinner elections have proven to be a fruitful research topic with many real-world applications. We contribute to this line of research by improving the state of the art regarding the computational complexity of computing good committees. More ...$\mathcal{}$$\mathcal{}$$\mathcal{}{}^{}$$\mathcal{}{\mathrm{}}^{}$

We present deterministic algorithms for maintaining a $(3/2+ϵ)$ and $(2+ϵ)$-approximate maximum matching in a fully dynamic graph with worst-case update times $\widehat{O}(\sqrt{n})$ and $\tilde{O}(1)$ respectively. The fastest known deterministic worst-case update time ...$\mathrm{}$$\mathrm{}$$\mathrm{}$${}^{\mathrm{}\mathrm{}}$${}_{}\sqrt{}$${}_{}\sqrt{}$$\stackrel{}{}\mathrm{}$$\mathrm{}\mathrm{}$$$$$$$$\mathrm{}\mathrm{}$$$$$$\stackrel{}{}\mathrm{}$$\stackrel{}{}\mathrm{}$$\mathrm{}$

In search problems, a mobile searcher seeks to locate a target that hides in some unknown position of the environment. Such problems are typically considered to be of an on-line nature, in that the target’s position is unknown to the searcher, and ...

Simple heuristics for (combinatorial) optimization problems often show a remarkable performance in practice. Worst-case analysis often falls short of explaining this performance. Because of this, “beyond worst-case analysis” of algorithms has ...$\mathrm{}{}^{}$$\mathrm{}\mathrm{}$$$

In this paper, we study two generalizations of Vertex Cover and Edge Cover, namely Colorful Vertex Cover and Colorful Edge Cover. In the Colorful Vertex Cover problem, given an n-vertex edge-colored graph G with colors from $\{1,\dots ,\omega \}$ and coverage ...${}_{\mathrm{}}{}_{\mathrm{}}{}_{}$${}_{}$$\mathrm{}$${}_{}$${}_{}$$\mathrm{}$$\mathrm{}$${}^{}$$\mathrm{}$${}^{\mathrm{}}$

Matrix permanents are hard to compute or even estimate in general. It had been previously suggested that the permanents of Positive Semidefinite (PSD) matrices may have efficient approximations. By relating PSD permanents to a task in quantum ...

We study opinion formation games based on the famous model proposed by Friedkin and Johsen (FJ model). In today’s huge social networks the assumption that in each round agents update their opinions by taking into account the opinions of all their ...${}_{}\mathrm{}\mathrm{}$${}_{}\mathrm{}\mathrm{}$${}_{}$${}_{\mathit{}}$${{}_{}{}_{}}^{\mathrm{}}$${{}_{}{}_{}}^{\mathrm{}}$$\mathrm{}$$$${}^{}$$\stackrel{}{}{}^{\mathrm{}}\mathrm{}$${}^{}$$$$\mathrm{}$

A function $f:V(G)\to \{0,1,2\}$ is called a Roman dominating function on $G=(V(G),E(G))$ if for every vertex v with $f(v)=0$, there exists a vertex $u\in N_G(v)$ such that $f(u)=2$. A function $f:V(G)\to \{0,1,2\}$ induces an ordered partition $(V_0,V_1,V_2)$ of V(G), where $V_i=...$$\mathrm{}\mathrm{}\mathrm{}$$\mathrm{}\mathrm{}\mathrm{}$${}_{\mathrm{}}{}_{\mathrm{}}{}_{\mathrm{}}$$\mathrm{}$${}_{}{}_{\mathrm{}}\mathrm{}$$\mathrm{}$${}_{}{}_{\mathrm{}}\mathrm{}$$\mathrm{}\mathrm{}\mathrm{}$${}_{}$${}_{}$${}^{\mathrm{}}$$\mathrm{}$$\mathsf{}\mathsf{}$$\mathrm{}$$$

Let $P=\{p_0,\dots ,p_{n-1}\}$ be a set of points in ${\mathbb{R}}^d$, modeling devices in a wireless network. A range assignment assigns a range $r(p_i)$ to each point $p_i\in P$, thus inducing a directed communication graph ${\mathcal{G}}_r$ in which there is a directed edge $(p_i,p_j)$ iff $\text{dist}(p_i,{\mathrm{...}}_{}{}_{}$${}_{}{}_{}$${}_{}$${}_{}$${\mathcal{}}_{}$${}_{{}_{}}{{}_{}}^{}$$\mathrm{}$${}_{}$${\mathcal{}}_{}$${}_{\mathrm{}}$

A well-known approach in the design of efficient algorithms, called matrix sparsification, approximates a matrix A with a sparse matrix $A^{\prime }$. Achlioptas and McSherry (J ACM 54(2):9-es, 2007) initiated a long line of work on spectral-norm ...${}^{}$$\mathrm{}$$$$$$$${}_{}$$$$$$$

A class of optimal three-weight $[q^k-1,k+1,q^{k-1}(q-1)-1]$ cyclic codes over ${\mathrm{I}\mathrm{F}}_q$, with $k\ge 2$, achieving the Griesmer bound, was presented by Heng and Yue (IEEE Trans Inf Theory 62(8):4501–4513, 2016. https://doi.org/10.1109/TIT.2016.2550029). In this ...$\mathrm{}$${\mathrm{}\mathrm{}}_{}$