Hierarchical Chinese Postman Problem: slightest disorder makes it hard, disconnectedness is manageable - Conference attendances

Hierarchical Chinese Postman Problem: slightest disorder makes it hard, disconnectedness is manageable Conference attendances

Language

Английский

Participant type

Секционный

URL

https://easychair.org/smart-program/MOTOR2021/2021-07-09.html#session:54121

Conference

Mathematical optimization theory and operations research (MOTOR-2021)
05-10 Jul 2021 , Иркутск

Authors

Афанасьев Всеволод Альбертович ² , Ван Беверн Рене Андреасович ² , Tsidulko Oxana Yurievna ¹

Affiliations

1	Sobolev Institute of Mathematics
2	Novosibirsk State University

The Hierarchical Chinese Postman Problem is finding a shortest traversal of all edges of a graph respecting precedence constraints given by a partial order on classes of edges. We show that the special case with connected classes is NP-hard even on orders decomposable into a chain and an incomparable class. For the case with linearly ordered (possibly disconnected) classes, we get 5/3-approximations and fixed-parameter algorithms by transferring results from the Rural Postman Problem.

Афанасьев В.А. , Ван Беверн Р.А. , Tsidulko O.Y.
Hierarchical Chinese Postman Problem: slightest disorder makes it hard, disconnectedness is manageable
Mathematical optimization theory and operations research (MOTOR-2021) 05-10 Jul 2021