George Christodoulou,Alkmini Sgouritsa,Bo Tang
George Christodoulou
We study the inefficiency of mixed Nash equilibria, expressed as the price of anarchy, of all-pay auctions in three different environments: combinatorial, multi-unit and single-item auctions. First, we consider item-bidding combinatorial au...
Nikhil Bansal,Parinya Chalermsook,Bundit Laekhanukit et al.
Nikhil Bansal et al.
In this paper, we develop new tools and connections for exponential time approximation. In this setting, we are given a problem instance and an integer r > 1 , and the goal is to design an approximation algorithm with the fastest possible ...
Zengfeng Huang,Pan Peng
Zengfeng Huang
In this paper we study graph problems in the dynamic streaming model, where the input is defined by a sequence of edge insertions and deletions. As many natural problems require Ω ( n ) space, where n is the number of vertices, existi...
On Singleton Arc Consistency for CSPs Defined by Monotone Patterns [0.03%]
单调模式定义的CSPs的Singleton弧一致性
Clément Carbonnel,David A Cohen,Martin C Cooper et al.
Clément Carbonnel et al.
Singleton arc consistency is an important type of local consistency which has been recently shown to solve all constraint satisfaction problems (CSPs) over constraint languages of bounded width. We aim to characterise all classes of CSPs de...
E Eiben,R Ganian,K Kangas et al.
E Eiben et al.
We consider the # P -complete problem of counting the number of linear extensions of a poset ( # LE ) ; a fundamental problem in order theory with applications in a variety of distinct areas. In particular, we study the complexity of # L...
Martijn van Ee,René Sitters
Martijn van Ee
The field of a priori optimization is an interesting subfield of stochastic combinatorial optimization that is well suited for routing problems. In this setting, there is a probability distribution over active sets, vertices that have to be...
The Impact of a Sparse Migration Topology on the Runtime of Island Models in Dynamic Optimization [0.03%]
迁移拓扑稀疏性对动态优化中岛模型运行时间的影响
Andrei Lissovoi,Carsten Witt
Andrei Lissovoi
Island models denote a distributed system of evolutionary algorithms which operate independently, but occasionally share their solutions with each other along the so-called migration topology. We investigate the impact of the migration topo...
How to Escape Local Optima in Black Box Optimisation: When Non-elitism Outperforms Elitism [0.03%]
如何逃离黑箱优化中的局部最优解：非精英策略优于精英策略的情形
Pietro S Oliveto,Tiago Paixão,Jorge Pérez Heredia et al.
Pietro S Oliveto et al.
Escaping local optima is one of the major obstacles to function optimisation. Using the metaphor of a fitness landscape, local optima correspond to hills separated by fitness valleys that have to be overcome. We define a class of fitness va...
Mark de Berg,Joachim Gudmundsson,Ali D Mehrabi
Mark de Berg
We study the following problem: preprocess a set O of objects into a data structure that allows us to efficiently report all pairs of objects from O that intersect inside an axis-aligned query range Q . We present data structures of size O ...
On Unrooted and Root-Uncertain Variants of Several Well-Known Phylogenetic Network Problems [0.03%]
关于几种众所周知的系统发育网络问题的无根和根不确定变体的研究
Leo van Iersel,Steven Kelk,Georgios Stamoulis et al.
Leo van Iersel et al.
The hybridization number problem requires us to embed a set of binary rooted phylogenetic trees into a binary rooted phylogenetic network such that the number of nodes with indegree two is minimized. However, from a biological point of view...