Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
From MaRDI portal
Publication:4173216
DOI10.1287/moor.2.3.209zbMath0391.90091OpenAlexW2143037347WikidataQ94768922 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 EfficiencyProbabilistic AnalysisPartitioning AlgorithmsTraveling Salesman in the Plane
Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Integer programming (90C10) Applications of graph theory to circuits and networks (94C15)
Related Items
Worst-Case Analysis of Network Design Problem Heuristics, 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, A multi-agent approach for solving traveling salesman problem, 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, On a new edge function on complete weighted graphs and its application for locating Hamiltonian cycles of small weight, A survey on combinatorial optimization in dynamic environments, Maximal paths in random dynamic graphs, Static pickup and delivery problems: a classification scheme and survey. (With comments and rejoinder), On properties of geometric random problems in the plane, Dynamic vehicle routing: Status and prospects, Quantizers ad the worst case Euclidean traveling salesman problem, The simultaneous semi-random model for TSP, A note on asymptotic formulae for one-dimensional network flow problems, Solving large-scale TSP using a fast wedging insertion partitioning approach, A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem, 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, Evaluation of Heuristic Algorithms for the TSP: A New Statistical Approach, A concentration inequality for the facility location problem, Learn global and optimize local: a data-driven methodology for last-mile routing, Multiple \(k\)-opt evaluation multiple \(k\)-opt moves with GPU high performance local search to large-scale traveling salesman problems, Continuous approximation models in freight distribution management, Computing the variance of tour costs over the solution space of the TSP in polynomial time, Iterated tour partitioning for Euclidean capacitated vehicle routing, Continuous approximation formulas for location problems, Inexactness and a future of computing, Unnamed Item, A lookahead partitioning heuristic for a new assignment and scheduling problem in a distribution system, Optimal transport methods for combinatorial optimization over two random point sets, Discrete extremal problems, Smoothed analysis of partitioning algorithms for Euclidean functionals, Probabilistic analysis of solving the assignment problem for the traveling salesman problem, Probabilistic analysis of combinatorial algorithms: A bibliography with selected annotations, Average performance of greedy heuristics for the integer knapsack problem., The Hamiltonian p-median problem, An O(N log N) planar travelling salesman heuristic based on spacefilling curves, Combining metaheuristics with mathematical programming, constraint programming and machine learning, An appraisal of computational complexity for operations researchers, A primer of the Euclidean Steiner problem, Light Euclidean Spanners with Steiner Points, Euclidean semi-matchings of random samples, Random shortest paths: non-Euclidean instances for metric optimization problems, Steiner minimal trees in rectilinear and octilinear planes, New scaling algorithms for the assignment and minimum mean cycle problems, Nested annealing: A provable improvement to simulated annealing, Combining metaheuristics with mathematical programming, constraint programming and machine learning, Survivable networks, linear programming relaxations and the parsimonious property, Competitive location in the plane, Unnamed Item, A comparison of problem decomposition techniques for the FAP, Probabilistic Analysis of Assignment Ranking: The Traveling Salesman Problems, On the Hamiltonicity Gap and doubly stochastic matrices, An approximate algorithm for a high-multiplicity parallel machine scheduling problem, Local search for the Steiner tree problem in the Euclidean plane, Combinatorial optimisation algorithms for a CAD workstation, NP-Complete operations research problems and approximation algorithms, Heuristic combinatorial optimization by simulated Darwinian evolution: A polynomial time algorithm for the traveling salesman problem, Geometric interpretation of Hamiltonian cycles problem via singularly perturbed Markov decision processes, Heuristic methods and applications: A categorized survey, The simple plant location problem: Survey and synthesis, Probabilistic Analysis of a Greedy Heuristic for Euclidean Matching, The asymptotic probabilistic behaviour of quadratic sum assignment problems, The 2004 Benjamin Franklin medal in computer and cognitive science presented to Richard M. Karp, IntraClusTSP -- an incremental intra-cluster refinement heuristic algorithm for symmetric travelling salesman problem, A partitioning algorithm for minimum weighted Euclidean matching, Hamiltonian cycle curves in the space of discounted occupational measures, Partitioning heuristics for two geometric maximization problems, Convergence of optimal stochastic bin packing, Polynomial-time instances of the minimum weight triangulation problem, Probabilistic Analysis of Geometric Location Problems, Rate of convergence for the Euclidean minimum spanning tree limit law, Probabilistic asymptotic properties of some combinatorial optimization problems
