P-Complete Approximation Problems

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

Cited In (only showing first 100 items - show all)

The asymptotic probabilistic behaviour of quadratic sum assignment problems
Improved approximations for TSP with simple precedence constraints
On random quadratic bottleneck assignment problems
Survivable networks, linear programming relaxations and the parsimonious property
Approximation algorithm for minimizing total latency in machine scheduling with deliveries
Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s)
Scheduling with bully selfish jobs
A performance guarantee heuristic for electronic components placement problems including thermal effects
Efficient PTAS for the maximum traveling salesman problem in a metric space of fixed doubling dimension
New linearizations of quadratic assignment problems
The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure
A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound
Implications of forbidden structures for extremal algorithmic problems
Non deterministic polynomial optimization problems and their approximations
An approximation algorithm for the general routing problem
Performance ratio of polynomial heuristics for triangle inequality quadratic assignment problems
On local search for the generalized graph coloring problem
Solving multi objective facility layout problem by modified simulated annealing
Four solution techniques for a general one machine scheduling problem. A comparative study
Global optimality conditions and optimization methods for quadratic assignment problems
The equilibrium generalized assignment problem and genetic algorithm
VERY STRONGLY CONSTRAINED PROBLEMS: AN ANT COLONY OPTIMIZATION APPROACH
Random Laplacian matrices and convex relaxations
On the landscape ruggedness of the quadratic assignment problem
Heuristic methods and applications: A categorized survey
An interactive layout heuristic based on hexagonal adjacency graphs
Optimization of the quadratic assignment problem using an ant colony algorithm
Biological computation of the solution to the quadratic assignment problem
Comparison of Quadratic Convex Reformulations to Solve the Quadratic Assignment Problem
Approximation algorithms for min-sum \(p\)-clustering
A branch-and-bound algorithm for the quadratic assignment problem based on the Hungarian method
A new formulation for the traveling deliveryman problem
One-dimensional machine location problems in a multi-product flowline with equidistant locations
An implementation of the iterated tabu search algorithm for the quadratic assignment problem
How to park freight trains on rail-rail transshipment yards: the train location problem
Selfish splittable flows and NP-completeness
On the quality of heuristic solutions to a 19\(\times 19\) quadratic assignment problem
Exact and heuristic solutions to minimize total waiting time in the blood products distribution problem
Domination analysis of some heuristics for the traveling salesman problem
A new linearization method for quadratic assignment problems
A survey on the structure of approximation classes
Lower bounds for the quadratic assignment problem via triangle decompositions
Bounds for the quadratic assignment problem using the bundle method
Massively parallel tabu search for the quadratic assignment problem
Optimizing simulated annealing schedules with genetic programming
Integer point sets minimizing average pairwise \(L_{1}\) distance: What is the optimal shape of a town?
An algorithm for quadratic assignment problems
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
Some global optimization problems on Stiefel manifolds
Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem
Global optimization of a class of nonconvex quadratically constrained quadratic programming problems
The adjacency relation on the traveling salesman polytope is NP-Complete
The complexity of designing a network with minimum diameter
A randomized approximation scheme for metric MAX-CUT
Reoptimization of minimum and maximum traveling salesman's tours
On improving convex quadratic programming relaxation for the quadratic assignment problem
On the computational complexity of centers locating in a graph
On the Average Case Complexity of Some P-complete Problems
Experimental analysis of crossover and mutation operators on the quadratic assignment problem
A complexity theory for feasible closure properties
Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median
Clustering heuristics for set covering
Quadratic assignment problems
Differential approximation of NP-hard problems with equal size feasible solutions
Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem
Completeness in approximation classes beyond APX
Effective formulation reductions for the quadratic assignment problem
Lower bounds for the quadratic assignment problem
The traveling salesman problem: An update of research
Communication-aware processor allocation for supercomputers: Finding point sets of small average distance
An approximation algorithm for max \(k\)-uncut with capacity constraints
On the refinement of bounds of heuristic algorithms for the traveling salesman problem
A very large-scale neighborhood search algorithm for the multi-resource generalized assignment problem
The complexity of the travelling repairman problem
A path relinking approach with ejection chains for the generalized assignment problem
Modeling and solving a bi-objective airport slot scheduling problem
Integrating combinatorial algorithms into a linear programming solver
Rolling horizon algorithms for a single-machine dynamic scheduling problem with sequence-dependent setup times
Machine scheduling with deliveries to multiple customer locations
Differential approximation results for the traveling salesman and related problems
A survey on combinatorial optimization in dynamic environments
Two classes of quadratic assignment problems that are solvable as linear assignment problems
Selected topics on assignment problems
On approximating the minimum independent dominating set
Copositive and semidefinite relaxations of the quadratic assignment problem
A branch-and-cut algorithm for quadratic assignment problems based on linearizations
A hybrid biased random key genetic algorithm for the quadratic assignment problem
Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems
The hardness of approximation: Gap location
Detailed layout planning for irregularly-shaped machines with transportation path design
Worst-Case Analysis of Network Design Problem Heuristics
On the solutions of stochastic traveling salesman problems
Canonical dual approach to solving the maximum cut problem
Clustering to minimize the maximum intercluster distance
The NPO-completeness of the longest Hamiltonian cycle problem
Structure preserving reductions among convex optimization problems
Recent advances for the quadratic assignment problem with special emphasis on instances that are difficult for meta-heuristic methods
On locating new facilities in a competitive environment
A survey for the quadratic assignment problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4119042)