Search

The maximum benefit Chinese postman problem (MBCPP) is a practical generalization of the Chinese postman problem. A distinctive feature of MBCPP is that the postman can traverse each edge arbitrary times and obtains a benefit for each traversal of an edge, which depends on the number of times that the edge has been traversed. (Pearn and Wang, Omega 31 (2003) 269–273) discussed MBCPP under the assumption that the benefits of each edge is a non-increasing function of the number of traversals. They showed that MBCPP under this assumption is NP-hard, and proposed a heuristic algorithm which applies the minimum spanning tree and the minimal-cost T-join algorithms. (Corberán, Plana, Rodríguez-Chía and Sanchis, Math. Program. 141 (2013) 21–48) presented an integer programming formulation and a branch-and-cut algorithm for MBCPP without the assumption on the benefits. This is based on the idea of integrating the benefits of each edge into two benefits, each representing that the edge is traversed an odd or even number of times. In this paper, by applying the idea of Corberán et al., we improve the heuristic algorithm of Pearn and Wang. Our algorithm applies to the general case with no assumption on the benefits, and can perform better even if the benefits are non-increasing. We then analyze the efficiency of our heuristic algorithm in theory and in practice, and prove that it finds the optimal solution when the benefits satisfy a certain property. [ABSTRACT FROM AUTHOR]

A graph is even (resp. odd) if all its vertex degrees are even (resp. odd). We consider edge coverings by prescribed number of even and/or odd subgraphs. In view of the 8-Flow Theorem, a graph admits a covering by three even subgraphs if and only if it is bridgeless. Coverability by three odd subgraphs has been characterized recently [Petruševski, M.; Škrekovski, R. Coverability of graph by three odd subgraphs. J. Graph Theory 2019, 92, 304–321]. It is not hard to argue that every acyclic graph can be decomposed into two odd subgraphs, which implies that every graph admits a decomposition into two odd subgraphs and one even subgraph. Here, we prove that every 3-edge-connected graph is coverable by two even subgraphs and one odd subgraph. The result is sharp in terms of edge-connectivity. We also discuss coverability by more than three parity regular subgraphs, and prove that it can be efficiently decided whether a given instance of such covering exists. Moreover, we deduce here a polynomial time algorithm which determines whether a given set of edges extends to an odd subgraph. Finally, we share some thoughts on coverability by two subgraphs and conclude with two conjectures.

We consider the s-t-path TSP: given a finite metric space with two elements s and t, we look for a path from s to t that contains all the elements and has minimum total distance. We improve the approximation ratio for this problem from 1.599 to 1.566. Like previous algorithms, we solve the natural LP relaxation and represent an optimum solution x∗ as a convex combination of spanning trees. Gao showed that there exists a spanning tree in the support of x∗ that has only one edge in each narrow cut [i.e., each cut C with x∗(C)<2]. Our main theorem says that the spanning trees in the convex combination can be chosen such that many of them are such “Gao trees” simultaneously at all sufficiently narrow cuts. [ABSTRACT FROM AUTHOR]