On the hardness of approximating the min-hack problem

DOI10.1007/S10878-005-1413-8zbMATH Open1079.90109OpenAlexW2024586985MaRDI QIDQ2569170FDOQ2569170

Authors: Ramkumar Chinchani, Duc Ha, Anusha Iyer, Shambhu Upadhyaya, Hung Q. Ngo 

Publication date: 18 October 2005

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-005-1413-8

Recommendations

• On the hardness of approximating minimization problems
• scientific article; zbMATH DE number 1954391
• On the hardness of approximating minimum vertex cover
• Hardness and approximation for network flow interdiction
• Publication:4502504

zbMATH Keywords

computer securityhardness of threat analysis

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Structure in Approximation Classes
• On the hardness of approximating minimization problems
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• On the hardness of approximating label-cover
• Minimum propositional proof length is NP-hard to linearly approximate
• On the hardness of approximating the min-hack problem
• PCP characterizations of NP: toward a polynomially-small error-probability

Cited In (4)

• On the hardness of approximating the min-hack problem
• Approximability of the k‐server disconnection problem
• Hardness and inapproximability of minimizing adaptive distinguishing sequences
• Mathematical Foundations of Computer Science 2004

This page was built for publication: On the hardness of approximating the min-hack problem

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