Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
From MaRDI portal
Publication:4173216
DOI10.1287/moor.2.3.209zbMath0391.90091WikidataQ94768922 ScholiaQ94768922MaRDI QIDQ4173216
Publication date: 1977
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/97b1ba1ae8850a787aec072eacc8a9da1fbfbad0
Computational Efficiency; Probabilistic Analysis; Partitioning Algorithms; Traveling Salesman in the Plane
90C35: Programming involving graphs or networks
05C35: Extremal problems in graph theory
90C10: Integer programming
94C15: Applications of graph theory to circuits and networks
Related Items
Geometric interpretation of Hamiltonian cycles problem via singularly perturbed Markov decision processes, Survivable networks, linear programming relaxations and the parsimonious property, Competitive location in the plane, Combinatorial optimisation algorithms for a CAD workstation, Heuristic combinatorial optimization by simulated Darwinian evolution: A polynomial time algorithm for the traveling salesman problem, A partitioning algorithm for minimum weighted Euclidean matching, Partitioning heuristics for two geometric maximization problems, A note on asymptotic formulae for one-dimensional network flow problems, The Hamiltonian p-median problem, Convergence of optimal stochastic bin packing, Probabilistic asymptotic properties of some combinatorial optimization problems, Maximal paths in random dynamic graphs, Quantizers ad the worst case Euclidean traveling salesman problem, Discrete extremal problems, Probabilistic analysis of solving the assignment problem for the traveling salesman problem, Probabilistic analysis of combinatorial algorithms: A bibliography with selected annotations, An O(N log N) planar travelling salesman heuristic based on spacefilling curves, An appraisal of computational complexity for operations researchers, A primer of the Euclidean Steiner problem, Euclidean semi-matchings of random samples, New scaling algorithms for the assignment and minimum mean cycle problems, Nested annealing: A provable improvement to simulated annealing, Polynomial-time instances of the minimum weight triangulation problem, Rate of convergence for the Euclidean minimum spanning tree limit law, The travelling salesman problem with pick-up and delivery, Boundary effects in the traveling salesperson problem, The general multi-retailer EOQ problem with vehicle routing costs, Average performance of greedy heuristics for the integer knapsack problem., Local search for the Steiner tree problem in the Euclidean plane, Heuristic methods and applications: A categorized survey, The simple plant location problem: Survey and synthesis, On properties of geometric random problems in the plane, Dynamic vehicle routing: Status and prospects, Divide and conquer strategies for parallel TSP heuristics, A hierarchical strategy for solving traveling salesman problems using elastic nets, Approximation algorithms for tree alignment with a given phylogeny, An introduction to population approaches for optimization and hierarchical objective functions: A discussion on the role of tabu search, The performance of forwards induction policies, Further results on the probabilistic traveling salesman problem, Steiner minimal trees in rectilinear and octilinear planes, The 2004 Benjamin Franklin medal in computer and cognitive science presented to Richard M. Karp, Static pickup and delivery problems: a classification scheme and survey. (With comments and rejoinder), Evaluation of Heuristic Algorithms for the TSP: A New Statistical Approach, Probabilistic Analysis of Assignment Ranking: The Traveling Salesman Problems, Probabilistic Analysis of a Greedy Heuristic for Euclidean Matching, A multi-agent approach for solving traveling salesman problem, The asymptotic probabilistic behaviour of quadratic sum assignment problems, Probabilistic Analysis of Geometric Location Problems, Worst-Case Analysis of Network Design Problem Heuristics, Unnamed Item, NP-Complete operations research problems and approximation algorithms
