Motivated by placement of jobs in physical machines, we introduce and analyze the problem of online recoloring, or online disengagement. In this problem, we are given a set of
n
weighted vertices and ...a
k
-coloring of the vertices (vertices represent jobs, and colors represent physical machines). Edges, representing conflicts between jobs, are inserted in an online fashion. After every edge insertion, the algorithm must output a proper
k
-coloring of the vertices. The cost of recoloring a vertex is the vertex’s weight. Our aim is to minimize the competitive ratio of the algorithm, i.e., the ratio between the cost paid by the online algorithm and the cost paid by an optimal, offline algorithm. We consider a couple of polynomially-solvable coloring variants. Specifically, for 2-coloring bipartite graphs we present an
O
(
log
n
)
-competitive deterministic algorithm and an
Ω
(
log
n
)
lower bound on the competitive ratio of randomized algorithms. For
(
Δ
+
1
)
-coloring, where
Δ
is the maximal node degree, we present tight bounds of
Θ
(
Δ
)
and
Θ
(
log
Δ
)
on the competitive ratios of deterministic and randomized algorithms, respectively (where
Δ
denotes the maximum degree). We also consider the fully dynamic case which allows edge deletions as well as insertions. All our algorithms are applicable to the case where vertices are arbitrarily weighted, and all our lower bounds hold even in the uniform weights (unweighted) case.
Naor M., Parter M., Yogev E.: (The power of distributed verifiers in interactive proofs. In: 31st ACM-SIAM symposium on discrete algorithms (SODA), pp 1096–115, 2020.
...https://doi.org/10.1137/1.9781611975994.67
) have recently demonstrated the existence of a
distributed interactive proof
for planarity (i.e., for certifying that a network is planar), using a sophisticated generic technique for constructing distributed IP protocols based on sequential IP protocols. The interactive proof for planarity is based on a distributed certification of the correct execution of any given sequential linear-time algorithm for planarity testing. It involves three interactions between the prover and the randomized distributed verifier (i.e., it is a dMAM protocol), and uses small certificates, on
O
(
log
n
)
bits in
n
-node networks. We show that a single interaction with the prover suffices, and randomization is unecessary, by providing an explicit description of a
proof-labeling scheme
for planarity, still using certificates on just
O
(
log
n
)
bits. We also show that there are no proof-labeling schemes—in fact, even no
locally checkable proofs
—for planarity using certificates on
o
(
log
n
)
bits.
One hope when using non-elitism in evolutionary computation is that the ability to abandon the current-best solution aids leaving local optima. To improve our understanding of this mechanism, we ...perform a rigorous runtime analysis of a basic non-elitist evolutionary algorithm (EA), the
(
μ
,
λ
)
EA, on the most basic benchmark function with a local optimum, the jump function. We prove that for all reasonable values of the parameters and the problem, the expected runtime of the
(
μ
,
λ
)
EA is, apart from lower order terms, at least as large as the expected runtime of its elitist counterpart, the
(
μ
+
λ
)
EA (for which we conduct the first runtime analysis on jump functions to allow this comparison). Consequently, the ability of the
(
μ
,
λ
)
EA to leave local optima to inferior solutions does not lead to a runtime advantage. We complement this lower bound with an upper bound that, for broad ranges of the parameters, is identical to our lower bound apart from lower order terms. This is the first runtime result for a non-elitist algorithm on a multi-modal problem that is tight apart from lower order terms.
The
(
1
+
(
λ
,
λ
)
)
genetic algorithm is a younger evolutionary algorithm trying to profit also from inferior solutions. Rigorous runtime analyses on unimodal fitness functions showed that it can ...indeed be faster than classical evolutionary algorithms, though on these simple problems the gains were only moderate. In this work, we conduct the first runtime analysis of this algorithm on a multimodal problem class, the jump functions benchmark. We show that with the right parameters, the
(
1
+
(
λ
,
λ
)
)
GA optimizes any jump function with jump size
2
≤
k
≤
n
/
4
in expected time
O
(
n
(
k
+
1
)
/
2
e
O
(
k
)
k
-
k
/
2
)
, which significantly and already for constant
k
outperforms standard mutation-based algorithms with their
Θ
(
n
k
)
runtime and standard crossover-based algorithms with their
O
~
(
n
k
-
1
)
runtime guarantee. For the isolated problem of leaving the local optimum of jump functions, we determine provably optimal parameters that lead to a runtime of
(
n
/
k
)
k
/
2
e
Θ
(
k
)
. This suggests some general advice on how to set the parameters of the
(
1
+
(
λ
,
λ
)
)
GA, which might ease the further use of this algorithm.
Twin-width and Polynomial Kernels Bonnet, Édouard; Kim, Eun Jung; Reinald, Amadeus ...
Algorithmica,
11/2022, Letnik:
84, Številka:
11
Journal Article
Recenzirano
Odprti dostop
We study the existence of polynomial kernels, for parameterized problems without a polynomial kernel on general graphs, when restricted to graphs of bounded twin-width. Our main result is that a ...polynomial kernel for
k
-Dominating Set
on graphs of twin-width at most 4 would contradict a standard complexity-theoretic assumption. The reduction is quite involved, especially to get the twin-width upper bound down to 4, and can be tweaked to work for
Connected
k
-Dominating Set
and
Total
k
-Dominating Set
(albeit with a worse upper bound on the twin-width). The
k
-Independent Set
problem admits the same lower bound by a much simpler argument, previously observed ICALP ’21, which extends to
k
-Independent Dominating Set
,
k
-Path
,
k
-Induced Path
,
k
-Induced Matching
, etc. On the positive side, we obtain a simple quadratic vertex kernel for
Connected
k
-Vertex Cover
and
Capacitated
k
-Vertex Cover
on graphs of bounded twin-width. Interestingly the kernel applies to graphs of Vapnik–Chervonenkis density 1, and does not require a witness sequence. We also present a more intricate
O
(
k
1.5
)
vertex kernel for
Connected
k
-Vertex Cover
. Finally we show that deciding if a graph has twin-width at most 1 can be done in polynomial time, and observe that most optimization/decision graph problems can be solved in polynomial time on graphs of twin-width at most 1.
We give a first polynomial-time algorithm for (
Weighted
)
Feedback Vertex Set
on graphs of bounded
maximum induced matching width
(mim-width). Explicitly, given a branch decomposition of mim-width
w
..., we give an
n
O
(
w
)
-time algorithm that solves
Feedback Vertex Set
. This provides a unified polynomial-time algorithm for many well-known classes, such as
Interval
graphs,
Permutation
graphs, and
Leaf power
graphs (given a leaf root), and furthermore, it gives the first polynomial-time algorithms for other classes of bounded mim-width, such as
Circular Permutation
and
Circular
k
-Trapezoid
graphs (given a circular
k
-trapezoid model) for fixed
k
. We complement our result by showing that
Feedback Vertex Set
is
W
1
-hard when parameterized by
w
and the hardness holds even when a linear branch decomposition of mim-width
w
is given.
We extend the techniques developed in Ivanyos
et al
. (Comput Complex 26(3):717–763,
2017
) to obtain a deterministic polynomial-time algorithm for computing the non-commutative rank of linear spaces ...of matrices over any field.
The key new idea that causes a reduction in the time complexity of the algorithm in Ivanyos
et al
. (
2017
) from exponential time to polynomial time is a reduction procedure that keeps the blow-up parameter small, and there are two methods to implement this idea: the first one is a greedy argument that removes certain rows and columns, and the second one is an efficient algorithmic version of a result of Derksen & Makam (Adv Math 310:44–63,
2017b
), who were the first to observe that the blow-up parameter can be controlled. Both methods rely crucially on the regularity lemma from Ivanyos
et al
. (
2017
). In this note, we improve that lemma by removing a coprime condition there.
We propose and analyze a self-adaptive version of the
(
1
,
λ
)
evolutionary algorithm in which the current mutation rate is encoded within the individual and thus also subject to mutation. A ...rigorous runtime analysis on the
OneMax
benchmark function reveals that a simple local mutation scheme for the rate leads to an expected optimization time (number of fitness evaluations) of
O
(
n
λ
/
log
λ
+
n
log
n
)
when
λ
is at least
C
ln
n
for some constant
C
>
0
. For all values of
λ
≥
C
ln
n
, this performance is asymptotically best possible among all
λ
-parallel mutation-based unbiased black-box algorithms. Our result rigorously proves for the first time that self-adaptation in evolutionary computation can find complex optimal parameter settings on the fly. In particular, it gives asymptotically the same performance as the relatively complicated self-adjusting scheme for the mutation rate proposed by Doerr, Gießen, Witt, and Yang (Algorithmica 2019). On the technical side, the paper contributes new tools for the analysis of two-dimensional drift processes arising in the analysis of dynamic parameter choices in EAs, including bounds on occupation probabilities in processes with non-constant drift.
The constraint satisfaction problem (CSP) on a finite relational structure
B
is to decide, given a set of constraints on variables where the relations come from
B
, whether or not there is an ...assignment to the variables satisfying all of the constraints; the surjective CSP is the variant where one decides the existence of a surjective satisfying assignment onto the universe of
B
. We present an algebraic framework for proving hardness results on surjective CSPs; essentially, this framework computes global gadgetry that permits one to present a reduction from a classical CSP to a surjective CSP. We show how to derive a number of hardness results for surjective CSP in this framework, including the hardness of the disconnected cut problem, of the no-rainbow three-coloring problem, and of the surjective CSP on all two-element structures known to be intractable (in this setting). Our framework thus allows us to unify these hardness results and reveal common structure among them; we believe that our hardness proof for the disconnected cut problem is more succinct than the original. In our view, the framework also makes very transparent a way in which classical CSPs can be reduced to surjective CSPs.
PDF
