Approximation Algorithms for Some Postman Problems
From MaRDI portal
Publication:4191881
DOI10.1145/322139.322150zbMath0405.90076OpenAlexW2062403584MaRDI QIDQ4191881
Publication date: 1979
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322139.322150
Traveling Salesman ProblemHeuristic AlgorithmRural Postman ProblemChinese Postman ProblemNp-Complete ProblemEstimation of Execution TimePostman ProblemWorst-Case Behavior
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10)
Related Items (49)
Algorithms for the windy postman problem ⋮ Approximation algorithms for solving the constrained arc routing problem in mixed graphs ⋮ A polyhedral approach to the rural postman problem ⋮ A capacitated general routing problem on mixed networks ⋮ Algorithms for the Chinese postman problem on mixed networks ⋮ Rural postman parameterized by the number of components of required edges ⋮ A LP-based approximation algorithm for generalized traveling salesperson path problem ⋮ Designing networks with compact routing tables ⋮ New heuristic algorithms for the windy rural postman problem ⋮ A biased random-key genetic algorithm for the capacitated minimum spanning tree problem ⋮ Computational comparison of several greedy algorithms for the minimum cost perfect matching problem on large graphs ⋮ Algorithms for the rural postman problem ⋮ Routing problems: A bibliography ⋮ On a routing and scheduling problem concerning multiple edge traversals in graphs ⋮ A note on approximation algorithms of the clustered traveling salesman problem ⋮ Eulerian location problems ⋮ On the windy postman problem on Eulerian graphs ⋮ The commodity-split multi-compartment capacitated arc routing problem ⋮ A new view on rural postman based on Eulerian extension and matching ⋮ Approximation algorithms for the min-max clustered \(k\)-traveling salesmen problems ⋮ Arc routing problems: A review of the past, present, and future ⋮ An LP-based approximation algorithm for the generalized traveling salesman path problem ⋮ Approximation Algorithms for a Mixed Postman Problem with Restrictions on the Arcs ⋮ Approximation algorithms for the min-max mixed rural postmen cover problem and its variants ⋮ Approximation algorithms for the min-max mixed rural postmen cover problem and its variants ⋮ Improving a constructive heuristic for the general routing problem ⋮ The single robot line coverage problem: Theory, algorithms, and experiments ⋮ A heuristic algorithm based on Monte Carlo methods for the rural postman problem. ⋮ An improved approximation algorithm for the clustered traveling salesman problem ⋮ Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems ⋮ A deterministic tabu search algorithm for the capacitated arc routing problem ⋮ Approximation algorithms for some min-max postmen cover problems ⋮ A Decade of Capacitated Arc Routing ⋮ Min-max cover of a graph with a small number of parts ⋮ An approximation algorithm for the general routing problem ⋮ Capacitated arc routing problem with deadheading demands ⋮ Recent results on Arc Routing Problems: An annotated bibliography ⋮ Efficient Algorithms for Eulerian Extension ⋮ A 3/2-Approximation Algorithm for the Multiple TSP with a Fixed Number of Depots ⋮ OAR lib: an open source arc routing library ⋮ Approximation Algorithms for the Single Robot Line Coverage Problem ⋮ Differential approximation of NP-hard problems with equal size feasible solutions ⋮ Heuristic methods and applications: A categorized survey ⋮ From Few Components to an Eulerian Graph by Adding Arcs ⋮ An extension of Christofides heuristic to the k-person travelling salesman problem ⋮ Approximation algorithms with constant ratio for general cluster routing problems ⋮ Heuristics for the rural postman problem ⋮ A GRASP heuristic for the mixed Chinese postman problem ⋮ On the mixed Chinese postman problem
This page was built for publication: Approximation Algorithms for Some Postman Problems
