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)

Recognising permuted Demidenko matrices
Fast Distributed Approximation for Max-Cut
Computational topology and the unique games conjecture
Max cut and semidefinite rank
Title not available (Why is that?)
A CONTINUATION APPROACH USING NCP FUNCTION FOR SOLVING MAX-CUT PROBLEM
Strongly connected spanning subgraph for almost symmetric networks
An experimental evaluation of semidefinite programming and spectral algorithms for max cut
A tissue P system based solution to quadratic assignment problem
Approximation performance of ant colony optimization for the \(\mathrm{TSP}(1,2)\) problem
An LP-based approximation algorithm for the generalized traveling salesman path problem
Approximating asymmetric TSP in exponential time
Localization in 1D non-parametric latent space models from pairwise affinities
Title not available (Why is that?)
The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem
An optimization approach for hybrid workflows in platform-enabled private service marketplaces
The zone-based dynamic facility layout problem
A New Neighborhood for the QAP
Gilmore-Lawler bound of quadratic assignment problem
Unique optimal solution instance and computational complexity of backbone in the graph bi-partitioning problem
FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM
Improved approximations for hard optimization problems via problem instance classification
Better Process Mapping and Sparse Quadratic Assignment
Computational methods for solving nonconvex block-separable constrained quadratic problems
A domination algorithm for \(\{0,1\}\)-instances of the travelling salesman problem
Improving a state‐of‐the‐art heuristic for the minimum latency problem with data mining
Finite element approximation of data-driven problems in conductivity
Prize-collecting asymmetric traveling salesman problem admits polynomial time approximation within a constant ratio
Polynomial-time approximability of the asymmetric problem of covering a graph by a bounded number of cycles
Automatic generation of dominance breaking nogoods for a class of constraint optimization problems
Partial neighborhood local searches
Multi- and many-objective path-relinking: a taxonomy and decomposition approach
Scheduling on a graph with release times
Greedy heuristic guided by lexicographic excellence
A polynomial-time approximation scheme for the maximal overlap of two independent Erdős-Rényi graphs
Title not available (Why is that?)
Plowing with precedence in polynomial time
An experimental study of variable depth search algorithms for the quadratic assignment problem
A maximum hypergraph 3-cut problem with limited unbalance: approximation and analysis
Forward backward transformation
Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the asymmetric traveling salesman problem
Length-constrained cycle partition with an application to UAV routing*
Bilinear Assignment Problem: Large Neighborhoods and Experimental Analysis of Algorithms
From Graph Orientation to the Unweighted Maximum Cut
Level 2 Reformulation Linearization Technique–Based Parallel Algorithms for Solving Large Quadratic Assignment Problems on Graphics Processing Unit Clusters
Structural properties of hard metric TSP inputs (extended abstract)
Approximation schemes for Min-Sum \(k\)-Clustering
Facility layout problem with QAP formulation under scenario-based uncertainty
Probabilistic stopping rules for GRASP heuristics and extensions
Exact recovery with symmetries for the doubly stochastic relaxation
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

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)