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
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
