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

An extreme point algorithm for a local minimum solution to the quadratic assignment problem, The hardness of approximation: Gap location, Lower bounds for the quadratic assignment problem, Metric violation distance: hardness and approximation, A study of diversification strategies for the quadratic assignment problem, On residual approximation in solution extension problems, A new exact algorithm for the solution of quadratic assignment problems, Approximation and complexity of multi-target graph search and the Canadian traveler problem, On an approximation measure founded on the links between optimization and polynomial approximation theory, Solving multi objective facility layout problem by modified simulated annealing, A LP-based approximation algorithm for generalized traveling salesperson path problem, A problem evolution algorithm with linear programming for the dynamic facility layout problem -- a general layout formulation, A branch-and-price algorithm for the minimum latency problem, Tabu search and iterated local search for the cyclic bottleneck assignment problem, A modification of threshold accepting and its application to the quadratic assignment problem, Efficient PTAS for the maximum traveling salesman problem in a metric space of fixed doubling dimension, A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems, Lower bounds for the quadratic assignment problem via triangle decompositions, Effects of scatter plot initial solutions on regular grid facility layout algorithms in typical production models, Optimal sequences in stochastic single machine shops, The quadratic cycle cover problem: special cases and efficient bounds, General network design: a unified view of combined location and network design problems, A simple and effective metaheuristic for the minimum latency problem, A \(\beta\)-accurate linearization method of Euclidean distance for the facility layout problem with heterogeneous distance metrics, Lower bounds for the quadratic semi-assignment problem, Determining matchdays in sports league schedules to minimize rest differences, A cutoff time strategy based on the coupon collector's problem, Locating names on vertices of a transaction network, The bilinear assignment problem: complexity and polynomially solvable special cases, A new greedy algorithm for the quadratic assignment problem, Submodular optimization problems and greedy strategies: a survey, Solving the continuous flow-shop scheduling problem by metaheuristics., FACOPT: A user friendly FACility layout OPTimization system., Solving the quadratic assignment problem, Compact linearization for binary quadratic problems subject to assignment constraints, An exact algorithm for the minimum squared load assignment problem, Minimizing latency in post-disaster road clearance operations, Semidefinite programming approach for the quadratic assignment problem with a sparse graph, Polynomial-time approximation algorithm for the problem of cardinality-weighted variance-based 2-clustering with a given center, Random Laplacian matrices and convex relaxations, An exact solution method for quadratic matching: the one-quadratic-term technique and generalisations, 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, New special cases of the quadratic assignment problem with diagonally structured coefficient matrices, On the complexity of generating synchronizable test sequences, Embedding signed graphs in the line, An interactive layout heuristic based on hexagonal adjacency graphs, Genetic algorithms, function optimization, and facility layout design, Multi-level departments-to-offices assignment with different room types, Solving a group layout design model of a dynamic cellular manufacturing system with alternative process routings, lot splitting and flexible reconfiguration by simulated annealing, Topological arrangements of \(M/G/c/K\), \(M/G/c/c\) queues in transportation and material handling systems, New linearizations of quadratic assignment problems, A discrete dynamic convexized method for the max-cut problem, Minimizing the average searching time for an object within a graph, Approximation algorithms for some vehicle routing problems, Complexity of the directed spanning cactus problem, A 4-approximation algorithm for the TSP-path satisfying a biased triangle inequality, Some global optimization problems on Stiefel manifolds, Polynomial approximation algorithms with performance guarantees: an introduction-by-example, Approximation algorithms for general cluster routing problem, A performance guarantee heuristic for electronic components placement problems including thermal effects, A parallel heuristic for quadratic assignment problems, Constant-factor approximations for capacitated arc routing without triangle inequality, On the integrality ratio of the subtour LP for Euclidean TSP, The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure, A proximal DC approach for quadratic assignment problem, Quadratic assignment problem variants: a survey and an effective parallel memetic iterated tabu search, Four solution techniques for a general one machine scheduling problem. A comparative study, On the solutions of stochastic traveling salesman problems, A local search algorithm for binary maximum 2-path partitioning, Sequential Monte Carlo for maximum weight subgraphs with application to solving image jigsaw puzzles, 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, Heuristic methods and applications: A categorized survey, 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, Approximation algorithms with constant ratio for general cluster routing problems, 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, An effective implementation of the Lin-Kernighan traveling salesman heuristic, Clustering heuristics for set covering, Distributed task assignment using critical path estimate, Solving the traveling delivery person problem with limited computational time, Approximation algorithms for some extensions of the maximum profit routing problem, 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, 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, Approximating the maximum quadratic assignment problem, Intelligent local search strategies for solving facility layout problems with the quadratic assignment problem formulation, On local search for the generalized graph coloring problem, 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, Facility layout problem with QAP formulation under scenario-based uncertainty, The zone-based dynamic facility layout problem, An efficient algorithm for unequal area facilities layout planning with input and output points, Unnamed Item, Better Process Mapping and Sparse Quadratic Assignment, Gilmore-Lawler bound of quadratic assignment problem, A maximum hypergraph 3-cut problem with limited unbalance: approximation and analysis, Improving a state‐of‐the‐art heuristic for the minimum latency problem with data mining, Automatic generation of dominance breaking nogoods for a class of constraint optimization problems, FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM, Partial neighborhood local searches, Plowing with precedence in polynomial time, A Survey of the Generalized Assignment Problem and Its Applications, The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem, Sinkhorn Algorithm for Lifted Assignment Problems, An optimization approach for hybrid workflows in platform-enabled private service marketplaces, Prize-collecting asymmetric traveling salesman problem admits polynomial time approximation within a constant ratio, Localization in 1D non-parametric latent space models from pairwise affinities, Polynomial-time approximability of the asymmetric problem of covering a graph by a bounded number of cycles, Scheduling on a graph with release times, Unnamed Item, Local Search Algorithms for the Maximal Planar Layout Problem, Collapsing Superstring Conjecture, APPROXIMATING ASYMMETRIC TSP IN EXPONENTIAL TIME, On the landscape ruggedness of the quadratic assignment problem, Cardinality of relations and relational approximation algorithms, Complete Description of Matching Polytopes with One Linearized Quadratic Term for Bipartite Graphs, A Branch-Price-and-Cut Algorithm for Packing Cuts in Undirected Graphs, A multi-parent genetic algorithm for the quadratic assignment problem, Worst-Case Analysis of Network Design Problem Heuristics, On the Average Case Complexity of Some P-complete Problems, A complexity theory for feasible closure properties, Massively parallel tabu search for the quadratic assignment problem, Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems, Genetic algorithm for linear and cyclic assignment problem, The complexity of the travelling repairman problem, Ant colony optimization for solving an industrial layout problem, Approximation Algorithms for Min-Sum k-Clustering and Balanced k-Median, On the complexity of some quadratic Euclidean 2-clustering problems, Methods for Binary Multidimensional Scaling, Routing Under Uncertainty: The a priori Traveling Repairman Problem, Fast Distributed Approximation for Max-Cut, A survey on combinatorial optimization in dynamic environments, Length-constrained cycle partition with an application to UAV routing*, A very large-scale neighborhood search algorithm for the multi-resource generalized assignment problem, Exact Recovery with Symmetries for the Doubly Stochastic Relaxation, Sharp bounds for Karp's “patching”-algorithm for the approximate solution of the traveling salesman problem, A continuation algorithm for max-cut problem, Polynomial Time Approximation Scheme for Single-Depot Euclidean Capacitated Vehicle Routing Problem, A PTAS for MIN-\(k\)-SCCP in Euclidean space of arbitrary fixed dimension, NP-completeness: A retrospective, The approximation ratio of the 2-Opt heuristic for the metric traveling salesman problem, Multi- and many-objective path-relinking: a taxonomy and decomposition approach, Routing multiple work teams to minimize latency in post-disaster road network restoration, Integrating combinatorial algorithms into a linear programming solver, Two-level modified simulated annealing based approach for solving facility layout problem, An approximation algorithm for maxk-uncut with capacity constraints, A new approximation hierarchy for polynomial conic optimization, Unnamed Item, A New Neighborhood for the QAP, An LP-based approximation algorithm for the generalized traveling salesman path problem, A parallel water flow algorithm with local search for solving the quadratic assignment problem, Approximation performance of ant colony optimization for the TSP(1,2) problem, Comparison of Quadratic Convex Reformulations to Solve the Quadratic Assignment Problem, Exact pseudopolynomial algorithms for a balanced 2-clustering problem, Garden optimization problems for benchmarking quantum annealers, The Robust (Minmax Regret) Quadratic Assignment Problem with Interval Flows, Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the asymmetric traveling salesman problem, A New Composite Algorithm for Clustering Problems, THE THREE-PHASE METHOD: A UNIFIED APPROACH TO ORTHOGONAL GRAPH DRAWING, Randomized Decomposition Solver with the Quadratic Assignment Problem as a Case Study, Extending time‐to‐target plots to multiple instances, The Directed Minimum Latency Problem, Exact Algorithms for Distributionally β-Robust Machine Scheduling with Uncertain Processing Times, Level 2 Reformulation Linearization Technique–Based Parallel Algorithms for Solving Large Quadratic Assignment Problems on Graphics Processing Unit Clusters, Approximating the \(k\)-traveling repairman problem with repair times, Improved Approximations for Hard Optimization Problems via Problem Instance Classification, On the computational complexity of centers locating in a graph, An experimental study of variable depth search algorithms for the quadratic assignment problem, Knowing All Optimal Solutions Does Not Help for TSP Reoptimization, Communication-aware processor allocation for supercomputers: Finding point sets of small average distance, A layout design heuristic employing the theory of fuzzy sets, Unique optimal solution instance and computational complexity of backbone in the graph bi-partitioning problem, A TISSUE P SYSTEM BASED SOLUTION TO QUADRATIC ASSIGNMENT PROBLEM, Rolling horizon algorithms for a single-machine dynamic scheduling problem with sequence-dependent setup times, Probabilistic stopping rules for GRASP heuristics and extensions, Approximating Shortest Superstring Problem Using de Bruijn Graphs, Inclusion complete tally languages and the Hartmanis-Berman conjecture, An integrated approach for the concurrent determination of the block layout and the input and output point locations based on the contour distance, Computational topology and the Unique Games Conjecture, An integrated approach to determine the block layout, AGV flow path and the location of pick-up/delivery points in single-loop systems, The adjacency relation on the traveling salesman polytope is NP-Complete, 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, Toward solving the Steiner travelling salesman problem on urban road maps using the branch decomposition of graphs, A contribution to quadratic assignment problems, A new algorithm for solving a special matching problem with a general form value function under constraints, Sales‐delivery man problems on treelike networks, Structural Properties of Hard Metric TSP Inputs, Computational Methods for Solving Nonconvex Block-Separable Constrained Quadratic Problems, A domination algorithm for {0,1}-instances of the travelling salesman problem, Modeling and solving a bi-objective airport slot scheduling problem, From Graph Orientation to the Unweighted Maximum Cut, Bilinear Assignment Problem: Large Neighborhoods and Experimental Analysis of Algorithms, A priority based unbalanced time minimization assignment problem, Differential approximation of NP-hard problems with equal size feasible solutions, A CONTINUATION APPROACH USING NCP FUNCTION FOR SOLVING MAX-CUT PROBLEM, VERY STRONGLY CONSTRAINED PROBLEMS: AN ANT COLONY OPTIMIZATION APPROACH, The complexity of designing a network with minimum diameter, Forward Backward Transformation, The approximability of the weighted Hamiltonian path completion problem on a tree, Scalable Semidefinite Programming, A tabu search heuristic for the dynamic space allocation problem, Randomized algorithms for some hard-to-solve problems of clustering a finite set of points in Euclidean space, A path relinking approach with ejection chains for the generalized assignment problem, A new linearization method for quadratic assignment problems, The asymptotic probabilistic behaviour of quadratic sum assignment problems, A SIMULATED ANNEALING FOR INTRA-CELL LAYOUT DESIGN OF DYNAMIC CELLULAR MANUFACTURING SYSTEMS WITH ROUTE SELECTION, PURCHASING MACHINES AND CELL RECONFIGURATION, A study of stochastic local search algorithms for the biobjective QAP with correlated flow matrices, The traveling salesman problem: An update of research, On random quadratic bottleneck assignment problems, SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION ALGORITHMS, Strongly Connected Spanning Subgraph for Almost Symmetric Networks, A practical method for design of hybrid-type production facilities, An improved tabu search heuristic for solving facility layout design problems, On the refinement of bounds of heuristic algorithms for the traveling salesman problem, A quick method to compute sparse graphs for traveling salesman problem using random frequency quadrilaterals