The Eulerian Tour problem is of course a well-studied classical problem in graph theory (Wikipedia article). This question concerns non-Eulerian graphs; i.e., graphs that contain one or more odd-degree vertices. In a nutshell, I wonder what is the best "Eulerian-like" way of traversing non-Eulerian graphs.
Given an undirected connected graph, let an Eulerian "semi-tour" be defined as a "cycle" that passes each edge at least once and can visit any vertex or edge multiple times. Consider the following costs for a given semi-tour:
Total cost: The total number of edges visited by the semi-tour, counting multiplicities.
Width cost: The number of times the most-visited edge is visited.
I'm interested in optimization problems that aim to find a semi-tour that minimizes the total cost or the width cost on a given graph. Of course, if a graph is Eulerian, an Eulerian tour would be optimal, for which the total cost is the number of edges and the width cost is zero. For graphs containing odd degree vertices, the optimal cost in both senses must be larger.
I suspect these optimization problems (if not trivial) must have been well studied in the literature. What are the relevant references, if any, and what is known about these problems (both algorithmically and combinatorially)?
