Local search, reducibility and approximability of NP-optimization problems
type: Item
instance of: scholarly article
title: Local search, reducibility and approximability of NP-optimization problems
zbMATH Open document ID: 1022.68561
DOI: 10.1016/0020-0190(95)00006-X
published in: Information Processing Letters
publication date: 1997-02-28T00:00:00Z
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 985585
zbMATH Keywords: computational complexity
zbMATH Keywords: optimization
author: Giorgio Ausiello
author: Marco Protasi
MaRDI profile type: Publication
cites work: Q4230322
cites work: Approximate solution of NP optimization problems
cites work: Structure preserving reductions among convex optimization problems
cites work: Toward a unified approach for the classification of NP-complete optimization problems
cites work: Completeness in approximation classes
cites work: Q4470516
cites work: Q4198056
cites work: How easy is local search?
cites work: Q3320130
cites work: Q3677509
cites work: Optimization, approximation, and complexity classes
cites work: Non deterministic polynomial optimization problems and their approximations
full work available at URL: 0020-0190(95)00006-x
OpenAlex ID: W1975220965
Recommended article: Local search and the local structure of NP-complete problems
Recommended article: Q4871057
Recommended article: Q3059322
Recommended article: A note on the complexity of local search problems
Recommended article: Computational bounds for local search in combinatorial optimization
Recommended article: Q5501313
Recommended article: Approximate Local Search in Combinatorial Optimization
Recommended article: Q4407450
Recommended article: A Survey of Approximation Results for Local Search Algorithms
Recommended article: Q4864960
description: scientific article; zbMATH DE number 985585