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)

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
A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems
On an approximation measure founded on the links between optimization and polynomial approximation theory
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
The multi-story space assignment problem
A 4-approximation algorithm for the TSP-path satisfying a biased triangle inequality
General network design: a unified view of combined location and network design problems
A Survey of the Generalized Assignment Problem and Its Applications
Guaranteed performance heuristics for the bottleneck traveling salesman problem
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
Approximation algorithms for some vehicle routing problems
The delivery man problem on a tree network
The on-line asymmetric traveling salesman problem
Random assignment problems
An algorithm for the generalized quadratic assignment problem
Minimum-weight cycle covers and their approximability
The latency location-routing problem
Algorithm for the discrete Weber's problem with an accuracy estimate
Ant colony optimization algorithm to the inter-cell layout problem in cellular manufacturing
An improved approximation ratio for the minimum latency problem
An extreme point algorithm for a local minimum solution to the quadratic assignment problem
Easy and hard bottleneck location problems
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
Exact approaches for static data segment allocation problem in an information network
Exact pseudo-polynomial algorithms for a balanced 2-clustering problem
The facility layout problem
A nonlinear optimization approach for solving facility layout problems
Recent models and techniques for solving the layout problem
A nonmonotone GRASP
Flexible machine layout design for dynamic and uncertain production environments
A hybrid tabu search/branch \& bound approach to solving the generalized assignment problem
NP-completeness: a retrospective
Probabilistic asymptotic properties of some combinatorial optimization problems
QAPLIB-A quadratic assignment problem library
A discrete dynamic convexized method for the max-cut problem
A low-rank bilinear programming approach for sub-optimal solution of the quadratic assignment problem
A polynomially solvable class of quadratic semi-assignment problems
A contribution to quadratic assignment problems
Lower bounds for the quadratic semi-assignment problem
Topological arrangements of \(M/G/c/K\), \(M/G/c/c\) queues in transportation and material handling systems
Algodesk: An experimental comparison of eight evolutionary heuristics applied to the quadratic assignment problem
Analysis of Christofides' heuristic: some paths are more difficult than cycles
Genetic algorithms, function optimization, and facility layout design
A new approximation hierarchy for polynomial conic optimization
A stochastic and dynamic routing policy using branching processes with state dependent immigration
A study of diversification strategies for the quadratic assignment problem
Solving the continuous flow-shop scheduling problem by metaheuristics.
A parallel depth first search branch and bound algorithm for the quadratic assignment problem
Iterated local search for the quadratic assignment problem
An effective implementation of the Lin-Kernighan traveling salesman heuristic
Intelligent local search strategies for solving facility layout problems with the quadratic assignment problem formulation
A simple and effective metaheuristic for the minimum latency problem
Knowing all optimal solutions does not help for TSP reoptimization
Approximating the \(k\)-traveling repairman problem with repair times
Minimizing latency in post-disaster road clearance operations
Hybrid population-based algorithms for the bi-objective quadratic assignment problem
SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION ALGORITHMS
A study of stochastic local search algorithms for the biobjective QAP with correlated flow matrices
Ant colony optimization for solving an industrial layout problem
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

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)