P-Complete Approximation Problems

DOI10.1145/321958.321975zbMath0348.90152OpenAlexW2086917808WikidataQ56442576 ScholiaQ56442576MaRDI QIDQ4119042

Sartaj K. Sahni, Teofilo F. Gonzalez

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

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Nonlinear programming (90C30) Formal languages and automata (68Q45) Deterministic network models in operations research (90B10) General topics in the theory of software (68N01)

Related Items (only showing first 100 items - show all)

An asymptotically exact polynomial algorithm for equipartition problems ⋮ A unified FFT-based approach to maximum assignment problems related to transitive finite group actions ⋮ Performance ratio of polynomial heuristics for triangle inequality quadratic assignment problems ⋮ Implications of forbidden structures for extremal algorithmic problems ⋮ A hybrid biased random key genetic algorithm for the quadratic assignment problem ⋮ The principle of optimality in the design of efficient algorithms ⋮ Copositive and semidefinite relaxations of the quadratic assignment problem ⋮ The NPO-completeness of the longest Hamiltonian cycle problem ⋮ The facility layout problem ⋮ Differential approximation results for the traveling salesman and related problems ⋮ Layouts with wires of balanced length ⋮ On a new edge function on complete weighted graphs and its application for locating Hamiltonian cycles of small weight ⋮ A biased random-key genetic algorithm for the unequal area facility layout problem ⋮ The latency location-routing problem ⋮ A survey for the quadratic assignment problem ⋮ Algorithm for the discrete Weber's problem with an accuracy estimate ⋮ Approximability of the minimum-weight \(k\)-size cycle cover problem ⋮ Hardness of reoptimization of the problem of calculating the chromatic number of a graph with a given set of optimal solutions ⋮ 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 ⋮ Exact approaches for static data segment allocation problem in an information network ⋮ A nonmonotone GRASP ⋮ Constant factor approximation algorithm for TSP satisfying a biased triangle inequality ⋮ An approximation algorithm for the balanced Max-3-Uncut problem using complex semidefinite programming rounding ⋮ Optimization of the quadratic assignment problem using an ant colony algorithm ⋮ Bounds for the quadratic assignment problem using the bundle method ⋮ Quadratic assignment problems ⋮ 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 ⋮ The multi-story space assignment problem ⋮ Easy and hard bottleneck location problems ⋮ Improved approximations for TSP with simple precedence constraints ⋮ Pattern matching with wildcards and length constraints using maximum network flow ⋮ Integer point sets minimizing average pairwise \(L_{1}\) distance: What is the optimal shape of a town? ⋮ Structure preserving reductions among convex optimization problems ⋮ Global optimality conditions and optimization methods for quadratic assignment problems ⋮ The equilibrium generalized assignment problem and genetic algorithm ⋮ Non deterministic polynomial optimization problems and their approximations ⋮ Optimization problems and the polynomial hierarchy ⋮ Discrete extremal problems ⋮ NP-hardness of some quadratic Euclidean 2-clustering problems ⋮ How to park freight trains on rail-rail transshipment yards: the train location problem ⋮ An implementation of the iterated tabu search algorithm for the quadratic assignment problem ⋮ Exact and heuristic solutions to minimize total waiting time in the blood products distribution problem ⋮ Global optimization of a class of nonconvex quadratically constrained quadratic programming problems ⋮ An effective structured approach to finding optimal partitions of networks ⋮ The delivery man problem on a tree network ⋮ A survey on the structure of approximation classes ⋮ The complexity of drawing trees nicely ⋮ Approximation algorithm for minimizing total latency in machine scheduling with deliveries ⋮ Selfish splittable flows and NP-completeness ⋮ On locating new facilities in a competitive environment ⋮ Biological computation of the solution to the quadratic assignment problem ⋮ Single and multiple period layout models for automated manufacturing systems ⋮ The on-line asymmetric traveling salesman problem ⋮ Approximation results for the weighted \(P_4\) partition problem ⋮ Analysis of Christofides' heuristic: some paths are more difficult than cycles ⋮ Two classes of quadratic assignment problems that are solvable as linear assignment problems ⋮ Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median ⋮ Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem ⋮ Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem ⋮ A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph ⋮ Approximability of the problem about a minimum-weight cycle cover of a graph ⋮ Heuristic task assignment for distributed computing systems ⋮ On improving convex quadratic programming relaxation for the quadratic assignment problem ⋮ Experimental analysis of crossover and mutation operators on the quadratic assignment problem ⋮ Random assignment problems ⋮ Backbone analysis and algorithm design for the quadratic assignment problem ⋮ Survivable networks, linear programming relaxations and the parsimonious property ⋮ Scheduling with bully selfish jobs ⋮ Canonical dual approach to solving the maximum cut problem ⋮ Selected topics on assignment problems ⋮ Small space representations for metric min-sum \(k\)-clustering and their applications ⋮ Ant colony optimization algorithm to the inter-cell layout problem in cellular manufacturing ⋮ Effective formulation reductions for the quadratic assignment problem ⋮ Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s) ⋮ Machine scheduling with deliveries to multiple customer locations ⋮ Min sum clustering with penalties ⋮ The A priori traveling repairman problem ⋮ A hybrid tabu search/branch \& bound approach to solving the generalized assignment problem ⋮ Integrated slicing tree approach for solving the facility layout problem with input and output locations based on contour distance ⋮ Approximation algorithms for the bus evacuation problem ⋮ An algorithm for the generalized quadratic assignment problem ⋮ A new formulation for the traveling deliveryman problem ⋮ On approximating the minimum independent dominating set ⋮ Matrix columns allocation problems ⋮ Minimum-weight cycle covers and their approximability ⋮ Reoptimization of minimum and maximum traveling salesman's tours ⋮ Worst-case analysis of two travelling salesman heuristics ⋮ Guaranteed performance heuristics for the bottleneck traveling salesman problem ⋮ The optimum assignments and a new heuristic approach for the traveling salesman problem ⋮ On the quality of heuristic solutions to a 19\(\times 19\) quadratic assignment problem ⋮ Clustering to minimize the maximum intercluster distance ⋮ QAPLIB-A quadratic assignment problem library ⋮ Probabilistic asymptotic properties of some combinatorial optimization problems ⋮ A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound ⋮ Recent advances for the quadratic assignment problem with special emphasis on instances that are difficult for meta-heuristic methods

This page was built for publication: P-Complete Approximation Problems