Marten Folkertsma,Ian Mertz,Florian Speelman et al.
Marten Folkertsma et al.
A catalytic machine is a model of computation where a traditional space-bounded machine is augmented with an additional, significantly larger, "catalytic" tape, which, while being available as a work tape, has the caveat of being initialize...
Parameterized Complexities of Dominating and Independent Set Reconfiguration [0.03%]
图的支配集和独立集再定义问题的参数复杂性分析
Hans L Bodlaender,Carla Groenland,Céline M F Swennenhuis
Hans L Bodlaender
We settle the parameterized complexities of several variants of independent set reconfiguration and dominating set reconfiguration, parameterized by the number of tokens. We show that both problems are XL-complete when there is no limit on ...
The SLO Hierarchy of Pseudo-Boolean Functions and Runtime of Evolutionary Algorithms [0.03%]
伪布尔函数的SLO层次结构及进化算法的运行时间
Duc-Cuong Dang,Per Kristian Lehre
Duc-Cuong Dang
While some common fitness landscape characteristics are critical when determining the runtime of evolutionary algorithms (EAs), the relationship between fitness landscape structure and the runtime of EAs is poorly understood. Recently, Dang...
From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem [0.03%]
从数据补全到超立方体问题：独立集问题的参数化分析
Eduard Eiben,Robert Ganian,Iyad Kanj et al.
Eduard Eiben et al.
Several works have recently investigated the parameterized complexity of data completion problems, motivated by their applications in machine learning, and clustering in particular. Interestingly, these problems can be equivalently formulat...
A Clique-Based Separator for Intersection Graphs of Geodesic Disks in [Formula: see text] [0.03%]
基于盘状 clique 的 [Formula: see text] 中 geodesic 盘交图的分割点算法
Boris Aronov,Mark de Berg,Leonidas Theocharous
Boris Aronov
Let d be a (well-behaved) shortest-path metric defined on a path-connected subset of [Formula: see text] and let [Formula: see text] be a set of geodesic disks with respect to the metric d. We prove that [Formula: see text], the intersectio...
Smoothed Analysis of the 2-Opt Heuristic for the TSP under Gaussian Noise [0.03%]
具高斯噪声TSP的2-opt启发式算法的平滑分析
Marvin Künnemann,Bodo Manthey,Rianne Veenstra
Marvin Künnemann
The 2-opt heuristic is a very simple local search heuristic for the traveling salesperson problem. In practice it usually converges quickly to solutions within a few percentages of optimality. In contrast to this, its running-time is expone...
On the Parameterized Complexity of Eulerian Strong Component Arc Deletion [0.03%]
欧拉强分量弧删除问题的参数复杂度分析
Václav Blažej,Satyabrata Jana,M S Ramanujan et al.
Václav Blažej et al.
In this paper, we study the Eulerian Strong Component Arc Deletion problem, where the input is a directed multigraph and the goal is to delete the minimum number of arcs to ensure every strongly connected component of the resulting digraph ...
ShockHash: Near Optimal-Space Minimal Perfect Hashing Beyond Brute-Force [0.03%]
ShockHash：超越蛮力的几乎最优空间最小完美哈希算法
Hans-Peter Lehmann,Peter Sanders,Stefan Walzer
Hans-Peter Lehmann
A minimal perfect hash function (MPHF) maps a set S of n keys to the first n integers without collisions. There is a lower bound of n log 2 e - O ( log n ) ≈ 1.44 n bits needed to represent an MPHF. This can be reached by a brute-for...
Ioannis Mantas,Evanthia Papadopoulou,Rodrigo I Silveira et al.
Ioannis Mantas et al.
The farthest-color Voronoi diagram (FCVD) is defined on a set of n points in the plane, where each point is labeled with one of m colors. The colored points constitute a family P of m clusters (sets) of points in the plane whose farthest-si...
How Fitness Aggregation Methods Affect the Performance of Competitive CoEAs on Bilinear Problems [0.03%]
适应度聚合方法对竞争性合作协同进化算法求解双线性问题性能的影响研究
Mario Alejandro Hevia Fajardo,Per Kristian Lehre
Mario Alejandro Hevia Fajardo
Competitive co-evolutionary algorithms (CoEAs) do not rely solely on an external function to assign fitness values to sampled solutions. Instead, they use the aggregation of outcomes from interactions between competing solutions allowing to...