Weighted NP Optimization Problems: Logical Definability and Approximation Properties

DOI10.1137/S0097539795285102zbMATH Open0914.68074MaRDI QIDQ4210135FDOQ4210135

Authors: Marius Zimand 

Publication date: 21 September 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Recommendations

• Logical definability of NP optimization problems
• Parameterized complexity of weighted satisfiability problems
• scientific article; zbMATH DE number 847149
• scientific article; zbMATH DE number 1944142
• Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights
• On variable-weighted exact satisfiability problems
• Parameterized complexity of weighted satisfiability problems: decision, enumeration, counting
• SOFSEM 2005: Theory and Practice of Computer Science
• Publication:3484326
• scientific article; zbMATH DE number 515741

zbMATH Keywords

approximation propertiesNP optimization problemslogical definabilitymultiprover interactive systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (4)

• Title not available (Why is that?)
• Logical definability of NP optimization problems
• Approximation properties of NP minimization classes
• On weighted vs unweighted versions of combinatorial optimization problems

This page was built for publication: Weighted NP Optimization Problems: Logical Definability and Approximation Properties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210135)