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)

Communication-aware processor allocation for supercomputers: Finding point sets of small average distance
The traveling salesman problem: An update of research
Backbone analysis and algorithm design for the quadratic assignment problem
A new exact algorithm for the solution of quadratic assignment problems
A unified FFT-based approach to maximum assignment problems related to transitive finite group actions
An approximation algorithm for max \(k\)-uncut with capacity constraints
The approximability of the weighted Hamiltonian path completion problem on a tree
Exact recovery with symmetries for the doubly stochastic relaxation
Probabilistic stopping rules for GRASP heuristics and extensions
Layouts with wires of balanced length
Recognising permuted Demidenko matrices
Improved approximations for TSP with simple precedence constraints
A very large-scale neighborhood search algorithm for the multi-resource generalized assignment problem
The asymptotic probabilistic behaviour of quadratic sum assignment problems
Fast Distributed Approximation for Max-Cut
On the refinement of bounds of heuristic algorithms for the traveling salesman problem
Worst-case error bounds for parallel machine scheduling problems with bounded sequence-dependent setup times
Solving the traveling delivery person problem with limited computational time
Approximation algorithms for some extensions of the maximum profit routing problem
The complexity of the travelling repairman problem
Solving the quadratic assignment problem
Embedding signed graphs in the line
Exact algorithms for distributionally \(\beta \)-robust machine scheduling with uncertain processing times
Survivable networks, linear programming relaxations and the parsimonious property
Computational topology and the unique games conjecture
A path relinking approach with ejection chains for the generalized assignment problem
On random quadratic bottleneck assignment problems
Modeling and solving a bi-objective airport slot scheduling problem
Approximation algorithm for minimizing total latency in machine scheduling with deliveries
Integrating combinatorial algorithms into a linear programming solver
Methods for Binary Multidimensional Scaling
Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s)
An integrated approach to determine the block layout, AGV flow path and the location of pick-up/delivery points in single-loop systems
Small space representations for metric min-sum \(k\)-clustering and their applications
Scheduling with bully selfish jobs
Machine scheduling with deliveries to multiple customer locations
An integrated approach for the concurrent determination of the block layout and the input and output point locations based on the contour distance
Rolling horizon algorithms for a single-machine dynamic scheduling problem with sequence-dependent setup times
Max cut and semidefinite rank
Differential approximation results for the traveling salesman and related problems
A new greedy algorithm for the quadratic assignment problem
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
scientific article; zbMATH DE number 7092126 (Why is no real title available?)
Two classes of quadratic assignment problems that are solvable as linear assignment problems
A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound
Implications of forbidden structures for extremal algorithmic problems
The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure
An exact algorithm for the minimum squared load assignment problem
Selected topics on assignment problems
Collapsing Superstring Conjecture
A CONTINUATION APPROACH USING NCP FUNCTION FOR SOLVING MAX-CUT PROBLEM
A survey on combinatorial optimization in dynamic environments
Multi-level departments-to-offices assignment with different room types
Non deterministic polynomial optimization problems and their approximations
Min sum clustering with penalties
On approximating the minimum independent dominating set
Strongly connected spanning subgraph for almost symmetric networks
An approximation algorithm for the general routing problem
Cell formations in the uni-directional loop material handling environment
Copositive and semidefinite relaxations of the quadratic assignment problem
Pattern matching with wildcards and length constraints using maximum network flow
A hybrid biased random key genetic algorithm for the quadratic assignment problem
A branch-and-cut algorithm for quadratic assignment problems based on linearizations
Performance ratio of polynomial heuristics for triangle inequality quadratic assignment problems
On local search for the generalized graph coloring problem
A simulated annealing for intra-cell layout design of dynamic cellular manufacturing systems with route selection, purchasing machines and cell reconfiguration
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
Solving multi objective facility layout problem by modified simulated annealing
Simulated annealing for machine layout problems in the presence of zoning constraints
Determining matchdays in sports league schedules to minimize rest differences
Minimizing the average searching time for an object within a graph
Global optimality conditions and optimization methods for quadratic assignment problems
The equilibrium generalized assignment problem and genetic algorithm
Four solution techniques for a general one machine scheduling problem. A comparative study
An experimental evaluation of semidefinite programming and spectral algorithms for max cut
Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median
A tissue P system based solution to quadratic assignment problem
Data relaying with constraints in hierarchical sensor networks
Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems
Approximation performance of ant colony optimization for the \(\mathrm{TSP}(1,2)\) problem
Random Laplacian matrices and convex relaxations
VERY STRONGLY CONSTRAINED PROBLEMS: AN ANT COLONY OPTIMIZATION APPROACH
K-center and K-median problems in graded distances
The hardness of approximation: Gap location
Routing multiple work teams to minimize latency in post-disaster road network restoration
Detailed layout planning for irregularly-shaped machines with transportation path design
On residual approximation in solution extension problems
An LP-based approximation algorithm for the generalized traveling salesman path problem
A quick method to compute sparse graphs for traveling salesman problem using random frequency quadrilaterals
FACOPT: A user friendly FACility layout OPTimization system.
On the solutions of stochastic traveling salesman problems
Local Search Algorithms for the Maximal Planar Layout Problem
On the landscape ruggedness of the quadratic assignment problem
Worst-Case Analysis of Network Design Problem Heuristics
Heuristic methods and applications: A categorized survey
New special cases of the quadratic assignment problem with diagonally structured coefficient matrices
An asymptotically exact polynomial algorithm for equipartition problems

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)