Oswin Aichholzer,Jean Cardinal,Tony Huynh et al.
Oswin Aichholzer et al.
Flip graphs are a ubiquitous class of graphs, which encode relations on a set of combinatorial objects by elementary, local changes. Skeletons of associahedra, for instance, are the graphs induced by quadrilateral flips in triangulations of...
Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time [0.03%]
用于在确定性亚二次时间内找到离群相关性的显式相关放大器
Matti Karppa,Petteri Kaski,Jukka Kohonen et al.
Matti Karppa et al.
We derandomize Valiant's (J ACM 62, Article 13, 2015) subquadratic-time algorithm for finding outlier correlations in binary data. This demonstrates that it is possible to perform a deterministic subquadratic-time similarity join of high di...
Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness [0.03%]
计数导出子图：一个关于#W[1]-难问题的拓扑方法
Marc Roth,Johannes Schmitt
Marc Roth
We investigate the problem # IndSub ( Φ ) of counting all induced subgraphs of size k in a graph G that satisfy a given property Φ . This continues the work of Jerrum and Meeks who proved the problem to be # W [ 1 ] -hard for s...
Approximating Vector Scheduling: Almost Matching Upper and Lower Bounds [0.03%]
向量调度的近似算法：几乎相匹配的上界和下界
Nikhil Bansal,Tim Oosterwijk,Tjark Vredeveld et al.
Nikhil Bansal et al.
We consider the Vector Scheduling problem, a natural generalization of the classical makespan minimization problem to multiple resources. Here, we are given n jobs, represented as d-dimensional vectors in [ 0 , 1 ] d , and m identical mac...
Haris Aziz,Péter Biró,Serge Gaspers et al.
Haris Aziz et al.
We consider the two-sided stable matching setting in which there may be uncertainty about the agents' preferences due to limited information or communication. We consider three models of uncertainty: (1) lottery model-for each agent, there ...
Stable Matchings with Covering Constraints: A Complete Computational Trichotomy [0.03%]
具有覆盖限制的稳定匹配：计算三元性的完整分类
Matthias Mnich,Ildikó Schlotter
Matthias Mnich
Stable matching problems with lower quotas are fundamental in academic hiring and ensuring operability of rural hospitals. Only few tractable (polynomial-time solvable) cases of stable matching with lower quotas have been identified; most s...
Clemens Heuberger,Daniel Krenn
Clemens Heuberger
In this article, q-regular sequences in the sense of Allouche and Shallit are analysed asymptotically. It is shown that the summatory function of a regular sequence can asymptotically be decomposed as a finite sum of periodic fluctuations m...
On Easiest Functions for Mutation Operators in Bio-Inspired Optimisation [0.03%]
关于生物启发式优化中变异算子的最简函数
Dogan Corus,Jun He,Thomas Jansen et al.
Dogan Corus et al.
Understanding which function classes are easy and which are hard for a given algorithm is a fundamental question for the analysis and design of bio-inspired search heuristics. A natural starting point is to consider the easiest and hardest ...
A Runtime Analysis of Parallel Evolutionary Algorithms in Dynamic Optimization [0.03%]
动态参数优化中的并行进化算法的运行时间分析
Andrei Lissovoi,Carsten Witt
Andrei Lissovoi
A simple island model with λ islands and migration occurring after every τ iterations is studied on the dynamic fitness function Maze. This model is equivalent to a ( 1 + λ ) EA if τ = 1 , i. e., migration occurs durin...
Eduard Eiben,Robert Ganian,Stefan Szeider
Eduard Eiben
A modulator in a graph is a vertex set whose deletion places the considered graph into some specified graph class. The cardinality of a modulator to various graph classes has long been used as a structural parameter which can be exploited t...