P-Complete Approximation Problems

DOI10.1145/321958.321975zbMath0348.90152WikidataQ56442576 ScholiaQ56442576MaRDI QIDQ4119042

Teofilo F. Gonzalez, Sartaj K. Sahni

Publication date: 1976

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/321958.321975

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68Q25: Analysis of algorithms and problem complexity

90C10: Integer programming

90C30: Nonlinear programming

68Q45: Formal languages and automata

90B10: Deterministic network models in operations research

68N01: General topics in the theory of software

Related Items

Quadratic assignment problems, Survivable networks, linear programming relaxations and the parsimonious property, Selected topics on assignment problems, Ant colony optimization algorithm to the inter-cell layout problem in cellular manufacturing, Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s), Machine scheduling with deliveries to multiple customer locations, On approximating the minimum independent dominating set, Worst-case analysis of two travelling salesman heuristics, Guaranteed performance heuristics for the bottleneck traveling salesman problem, On the quality of heuristic solutions to a 19\(\times 19\) quadratic assignment problem, QAPLIB-A quadratic assignment problem library, Recent advances for the quadratic assignment problem with special emphasis on instances that are difficult for meta-heuristic methods, A survey for the quadratic assignment problem, Detailed layout planning for irregularly-shaped machines with transportation path design, A branch-and-cut algorithm for quadratic assignment problems based on linearizations, Data relaying with constraints in hierarchical sensor networks, Optimization of the quadratic assignment problem using an ant colony algorithm, Bounds for the quadratic assignment problem using the bundle method, The delivery man problem on a tree network, Approximation algorithm for minimizing total latency in machine scheduling with deliveries, Biological computation of the solution to the quadratic assignment problem, The on-line asymmetric traveling salesman problem, Approximation results for the weighted \(P_4\) partition problem, Random assignment problems, Backbone analysis and algorithm design for the quadratic assignment problem, An algorithm for the generalized quadratic assignment problem, A new formulation for the traveling deliveryman problem, The optimum assignments and a new heuristic approach for the traveling salesman problem, Clustering to minimize the maximum intercluster distance, Probabilistic asymptotic properties of some combinatorial optimization problems, A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound, An asymptotically exact polynomial algorithm for equipartition problems, Performance ratio of polynomial heuristics for triangle inequality quadratic assignment problems, Implications of forbidden structures for extremal algorithmic problems, The principle of optimality in the design of efficient algorithms, The facility layout problem, Layouts with wires of balanced length, Design of electronic assembly lines: An analytical framework and its application, Algodesk: An experimental comparison of eight evolutionary heuristics applied to the quadratic assignment problem, An algorithm for quadratic assignment problems, A parallel depth first search branch and bound algorithm for the quadratic assignment problem, Easy and hard bottleneck location problems, Structure preserving reductions among convex optimization problems, Non deterministic polynomial optimization problems and their approximations, Optimization problems and the polynomial hierarchy, Discrete extremal problems, An effective structured approach to finding optimal partitions of networks, The complexity of drawing trees nicely, On locating new facilities in a competitive environment, Single and multiple period layout models for automated manufacturing systems, Analysis of Christofides' heuristic: some paths are more difficult than cycles, Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem, Heuristic task assignment for distributed computing systems, Recent models and techniques for solving the layout problem, Flow network design for manufacturing systems layout, A nonlinear optimization approach for solving facility layout problems, Simulated annealing for machine layout problems in the presence of zoning constraints, An approximation algorithm for the general routing problem, On the complexity of generating synchronizable test sequences, An interactive layout heuristic based on hexagonal adjacency graphs, Genetic algorithms, function optimization, and facility layout design, Four solution techniques for a general one machine scheduling problem. A comparative study, On the solutions of stochastic traveling salesman problems, A neural network approach to facility layout problems, Optimizing simulated annealing schedules with genetic programming, K-center and K-median problems in graded distances, A polynomially solvable class of quadratic semi-assignment problems, A low-rank bilinear programming approach for sub-optimal solution of the quadratic assignment problem, A stochastic and dynamic routing policy using branching processes with state dependent immigration, Approximation algorithms for min-sum \(p\)-clustering, An improved approximation ratio for the minimum latency problem, One-dimensional machine location problems in a multi-product flowline with equidistant locations, Flexible machine layout design for dynamic and uncertain production environments, A branch-and-bound algorithm for the quadratic assignment problem based on the Hungarian method, Clustering heuristics for set covering, Distributed task assignment using critical path estimate, A heuristic for cyclic stochastic sequencing of tasks on a drum-like storage system, Worst-case error bounds for parallel machine scheduling problems with bounded sequence-dependent setup times, The hardness of approximation: Gap location, Lower bounds for the quadratic assignment problem, A study of diversification strategies for the quadratic assignment problem, A new exact algorithm for the solution of quadratic assignment problems, On an approximation measure founded on the links between optimization and polynomial approximation theory, Lower bounds for the quadratic semi-assignment problem, Solving the continuous flow-shop scheduling problem by metaheuristics., FACOPT: A user friendly FACility layout OPTimization system., An effective implementation of the Lin-Kernighan traveling salesman heuristic, Cell formations in the uni-directional loop material handling environment, Domination analysis of some heuristics for the traveling salesman problem, A randomized approximation scheme for metric MAX-CUT, Approximating the maximum quadratic assignment problem, Intelligent local search strategies for solving facility layout problems with the quadratic assignment problem formulation, Approximation algorithms for some vehicle routing problems, Complexity of the directed spanning cactus problem, Some global optimization problems on Stiefel manifolds, Polynomial approximation algorithms with performance guarantees: an introduction-by-example, A performance guarantee heuristic for electronic components placement problems including thermal effects, Heuristic methods and applications: A categorized survey, On local search for the generalized graph coloring problem, An extreme point algorithm for a local minimum solution to the quadratic assignment problem, On the Average Case Complexity of Some P-complete Problems, A New Composite Algorithm for Clustering Problems, Rolling horizon algorithms for a single-machine dynamic scheduling problem with sequence-dependent setup times, Differential approximation of NP-hard problems with equal size feasible solutions, Methods for Binary Multidimensional Scaling, An integrated approach for the concurrent determination of the block layout and the input and output point locations based on the contour distance, Sales‐delivery man problems on treelike networks, Local Search Algorithms for the Maximal Planar Layout Problem, On the landscape ruggedness of the quadratic assignment problem, A modification of threshold accepting and its application to the quadratic assignment problem, Lower bounds for the quadratic assignment problem via triangle decompositions, Optimal sequences in stochastic single machine shops, A parallel heuristic for quadratic assignment problems, A complexity theory for feasible closure properties, Massively parallel tabu search for the quadratic assignment problem, Genetic algorithm for linear and cyclic assignment problem, Ant colony optimization for solving an industrial layout problem, A very large-scale neighborhood search algorithm for the multi-resource generalized assignment problem, Approximating the \(k\)-traveling repairman problem with repair times, Communication-aware processor allocation for supercomputers: Finding point sets of small average distance, Unique optimal solution instance and computational complexity of backbone in the graph bi-partitioning problem, Iterated local search for the quadratic assignment problem, Completeness in approximation classes beyond APX, Hybrid population-based algorithms for the bi-objective quadratic assignment problem, The approximability of the weighted Hamiltonian path completion problem on a tree, A tabu search heuristic for the dynamic space allocation problem, A path relinking approach with ejection chains for the generalized assignment problem, A study of stochastic local search algorithms for the biobjective QAP with correlated flow matrices, A continuation algorithm for max-cut problem, THE THREE-PHASE METHOD: A UNIFIED APPROACH TO ORTHOGONAL GRAPH DRAWING, Unnamed Item, A layout design heuristic employing the theory of fuzzy sets, SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION ALGORITHMS, A contribution to quadratic assignment problems, A new linearization method for quadratic assignment problems, Two-level modified simulated annealing based approach for solving facility layout problem, A New Neighborhood for the QAP, The Directed Minimum Latency Problem, The asymptotic probabilistic behaviour of quadratic sum assignment problems, The traveling salesman problem: An update of research, On the refinement of bounds of heuristic algorithms for the traveling salesman problem, The complexity of the travelling repairman problem, Sharp bounds for Karp's “patching”-algorithm for the approximate solution of the traveling salesman problem, Unnamed Item, The complexity of designing a network with minimum diameter, On random quadratic bottleneck assignment problems, Worst-Case Analysis of Network Design Problem Heuristics, Inclusion complete tally languages and the Hartmanis-Berman conjecture, The adjacency relation on the traveling salesman polytope is NP-Complete, A practical method for design of hybrid-type production facilities, An improved tabu search heuristic for solving facility layout design problems