The
(
1
+
(
λ
,
λ
)
)
genetic algorithm proposed in Doerr et al. (Theor Comput Sci 567:87–104,
2015
) is one of the few examples for which a super-constant speed-up of the expected optimization time ...through the use of crossover could be rigorously demonstrated. It was proven that the expected optimization time of this algorithm on
OneMax
is
O
(
max
{
n
log
(
n
)
/
λ
,
λ
n
}
)
for any offspring population size
λ
∈
{
1
,
…
,
n
}
(and the other parameters suitably dependent on
λ
) and it was shown experimentally that a self-adjusting choice of
λ
leads to a better, most likely linear, runtime. In this work, we study more precisely how the optimization time depends on the parameter choices, leading to the following results on how to optimally choose the population size, the mutation probability, and the crossover bias both in a static and a dynamic fashion. For the mutation probability and the crossover bias depending on
λ
as in Doerr et al. (
2015
), we improve the previous runtime bound to
O
(
max
{
n
log
(
n
)
/
λ
,
n
λ
log
log
(
λ
)
/
log
(
λ
)
}
)
. This expression is minimized by a value of
λ
slightly larger than what the previous result suggested and gives an expected optimization time of
O
n
log
(
n
)
log
log
log
(
n
)
/
log
log
(
n
)
. We show that no static choice in the three-dimensional parameter space of offspring population, mutation probability, and crossover bias gives an asymptotically better runtime. We also prove that the self-adjusting parameter choice suggested in Doerr et al. (
2015
) outperforms all static choices and yields the conjectured linear expected runtime. This is asymptotically optimal among all possible parameter choices.
Intelligent transportation (e.g., intelligent traffic light) makes our travel more convenient and efficient. With the development of mobile Internet and position technologies, it is reasonable to ...collect spatio-temporal data and then leverage these data to achieve the goal of intelligent transportation, and here, traffic prediction plays an important role. In this paper, we provide a comprehensive survey on traffic prediction, which is from the spatio-temporal data layer to the intelligent transportation application layer. At first, we split the whole research scope into four parts from bottom to up, where the four parts are, respectively, spatio-temporal data, preprocessing, traffic prediction and traffic application. Later, we review existing work on the four parts. First, we summarize traffic data into five types according to their difference on spatial and temporal dimensions. Second, we focus on four significant data preprocessing techniques: map-matching, data cleaning, data storage and data compression. Third, we focus on three kinds of traffic prediction problems (i.e., classification, generation and estimation/forecasting). In particular, we summarize the challenges and discuss how existing methods address these challenges. Fourth, we list five typical traffic applications. Lastly, we provide emerging research challenges and opportunities. We believe that the survey can help the partitioners to understand existing traffic prediction problems and methods, which can further encourage them to solve their intelligent transportation applications.
Computing a (short) path between two vertices is one of the most fundamental primitives in graph algorithmics. In recent years, the study of paths in temporal graphs, that is, graphs where the vertex ...set is fixed but the edge set changes over time, gained more and more attention. A path is time-respecting, or
temporal
, if it uses edges with non-decreasing time stamps. We investigate a basic constraint for temporal paths, where the time spent at each vertex must not exceed a given duration
Δ
, referred to as
Δ
-
restless temporal paths
. This constraint arises naturally in the modeling of real-world processes like packet routing in communication networks and infection transmission routes of diseases where recovery confers lasting resistance. While finding temporal paths without waiting time restrictions is known to be doable in polynomial time, we show that the “restless variant” of this problem becomes computationally hard even in very restrictive settings. For example, it is W1-hard when parameterized by the
distance to disjoint path
of the underlying graph, which implies W1-hardness for many other parameters like feedback vertex number and pathwidth. A natural question is thus whether the problem becomes tractable in some natural settings. We explore several natural parameterizations, presenting FPT algorithms for three
kinds
of parameters: (1) output-related parameters (here, the maximum length of the path), (2) classical parameters applied to the underlying graph (e.g., feedback edge number), and (3) a new parameter called
timed feedback vertex number
, which captures finer-grained temporal features of the input temporal graph, and which may be of interest beyond this work.
We introduce multiplicative drift analysis as a suitable way to analyze the runtime of randomized search heuristics such as evolutionary algorithms. Our multiplicative version of the classical drift ...theorem allows easier analyses in the often encountered situation that the optimization progress is roughly proportional to the current distance to the optimum.
To display the strength of this tool, we regard the classical problem of how the (1+1) Evolutionary Algorithm optimizes an arbitrary linear pseudo-Boolean function. Here, we first give a relatively simple proof for the fact that any linear function is optimized in expected time
O
(
n
log
n
), where
n
is the length of the bit string. Afterwards, we show that in fact any such function is optimized in expected time at most (1+
o
(1))1.39e
n
ln
n
, again using multiplicative drift analysis. We also prove a corresponding lower bound of (1−
o
(1))e
n
ln
n
which actually holds for all functions with a unique global optimum.
We further demonstrate how our drift theorem immediately gives natural proofs (with better constants) for the best known runtime bounds for the (1+1) Evolutionary Algorithm on combinatorial problems like finding minimum spanning trees, shortest paths, or Euler tours in graphs.
In this work we consider
temporal networks
, i.e. networks defined by a
labeling
λ
assigning to each edge of an
underlying graph
G
a set of
discrete
time-labels. The labels of an edge, which are ...natural numbers, indicate the discrete time moments at which the edge is available. We focus on
path problems
of temporal networks. In particular, we consider
time-respecting
paths, i.e. paths whose edges are assigned by
λ
a strictly increasing sequence of labels. We begin by giving two efficient algorithms for computing shortest time-respecting paths on a temporal network. We then prove that there is a
natural analogue of Menger’s theorem
holding for arbitrary temporal networks. Finally, we propose two
cost minimization parameters
for temporal network design. One is the
temporality
of
G
, in which the goal is to minimize the maximum number of labels of an edge, and the other is the
temporal cost
of
G
, in which the goal is to minimize the total number of labels used. Optimization of these parameters is performed subject to some
connectivity constraint
. We prove several lower and upper bounds for the temporality and the temporal cost of some very basic graph families such as rings, directed acyclic graphs, and trees.
We study the parameterized complexity of the Bounded-Degree Vertex Deletion problem (BDD), where the aim is to find a maximum induced subgraph whose maximum degree is below a given degree bound. Our ...focus lies on parameters that measure the structural properties of the input instance. We first show that the problem is W1-hard parameterized by a wide range of fairly restrictive structural parameters such as the feedback vertex set number, pathwidth, treedepth, and even the size of a minimum vertex deletion set into graphs of pathwidth and treedepth at most three. We thereby resolve an open question stated in Betzler, Bredereck, Niedermeier and Uhlmann (2012) concerning the complexity of BDD parameterized by the feedback vertex set number. On the positive side, we obtain fixed-parameter algorithms for the problem with respect to the decompositional parameter treecut width and a novel problem-specific parameter called the core fracture number.
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.
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.
We propose a new way to self-adjust the mutation rate in population-based evolutionary algorithms in discrete search spaces. Roughly speaking, it consists of creating half the offspring with a ...mutation rate that is twice the current mutation rate and the other half with half the current rate. The mutation rate is then updated to the rate used in that subpopulation which contains the best offspring. We analyze how the
(
1
+
λ
)
evolutionary algorithm with this self-adjusting mutation rate optimizes the OneMax test function. We prove that this dynamic version of the
(
1
+
λ
)
EA finds the optimum in an expected optimization time (number of fitness evaluations) of
O
(
n
λ
/
log
λ
+
n
log
n
)
. This time is asymptotically smaller than the optimization time of the classic
(
1
+
λ
)
EA. Previous work shows that this performance is best-possible among all
λ
-parallel mutation-based unbiased black-box algorithms. This result shows that the new way of adjusting the mutation rate can find optimal dynamic parameter values on the fly. Since our adjustment mechanism is simpler than the ones previously used for adjusting the mutation rate and does not have parameters itself, we are optimistic that it will find other applications.
We introduce a novel adversarial model for scheduling with explorable uncertainty. In this model, the processing time of a job can potentially be reduced (by an
a priori
unknown amount) by testing ...the job. Testing a job
j
takes one unit of time and may reduce its processing time from the given upper limit
p
¯
j
(which is the time taken to execute the job if it is not tested) to any value between 0 and
p
¯
j
. This setting is motivated e.g., by applications where a code optimizer can be run on a job before executing it. We consider the objective of minimizing the sum of completion times on a single machine. All jobs are available from the start, but the reduction in their processing times as a result of testing is unknown, making this an online problem that is amenable to competitive analysis. The need to balance the time spent on tests and the time spent on job executions adds a novel flavor to the problem. We give the first and nearly tight lower and upper bounds on the competitive ratio for deterministic and randomized algorithms. We also show that minimizing the makespan is a considerably easier problem for which we give optimal deterministic and randomized online algorithms.
PDF
