The hardness of approximation: Gap location
type: Item
instance of: scholarly article
title: The hardness of approximation: Gap location
zbMATH Open document ID: 0822.68052
DOI: 10.1007/BF01202286
author: Erez Petrank
published in: Computational Complexity
publication date: 1994-09-01T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 627638
zbMATH Keywords: NP-hardness
zbMATH Keywords: gap location
zbMATH Keywords: NP-complete optimization problems
MaRDI profile type: Publication
cites work: Q4230372
cites work: Q4230321
cites work: Q4230322
cites work: The Steiner problem with edge lengths 1 and 2
cites work: Explicit constructions of linear-sized superconcentrators
cites work: The Complexity of Near-Optimal Graph Coloring
cites work: Q4198056
cites work: Some simplified NP-complete graph problems
cites work: The NP-Completeness of Edge-Coloring
cites work: Maximum bounded 3-dimensional matching is MAX SNP-complete
cites work: NP completeness of finding the chromatic index of regular graphs
cites work: On the hardness of approximating minimization problems
cites work: Q4071451
cites work: Optimization, approximation, and complexity classes
cites work: The Traveling Salesman Problem with Distances One and Two
cites work: P-Complete Approximation Problems
full work available at URL: https://doi.org/10.1007/bf01202286
OpenAlex ID: W3161056635
description: scientific article; zbMATH DE number 627638