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...
Daniel Funke,Demian Hespe,Peter Sanders et al.
Daniel Funke et al.
In bi-criteria optimization problems, the goal is typically to compute the set of Pareto-optimal solutions. Many algorithms for these types of problems rely on efficient merging or combining of partial solutions and filtering of dominated s...
Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-Turzík Bound [0.03%]
多重图中参数化最大裁剪问题的线性时间算法（超过Poljak-Turzik界的解）
Jonas Lill,Kalina Petrova,Simon Weber
Jonas Lill
MaxCut is a classical NP -complete problem and a crucial building block in many combinatorial algorithms. The famous Edwards-Erdös bound states that any connected graph on n vertices with m edges contains a cut of size at least m 2 + n - ...
Bodo Manthey,Jesse van Rhijn
Bodo Manthey
The 2-opt heuristic is a simple local search heuristic for the travelling salesperson problem (TSP). Although it usually performs well in practice, its worst-case running time is exponential in the number of cities. Attempts to reconcile th...