Approximating minimum keys and optimal substructure screens

DOI10.1007/3-540-61332-3_163MaRDI QIDQ6184674zbMATH OpenFDO

Authors Tatsuya Akutsu, Feng Bao

Publication date 29 January 2024

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-61332-3_163

Mathematics Subject Classification ID

Approximation algorithms (68W25) Analysis of algorithms (68W40) Combinatorial optimization (90C27)

Recommendations

• scientific article; zbMATH DE number 784428
• On the differential approximation of MIN SET COVER
• New and improved bounds for the minimum set cover problem
• Approximating the dense set-cover problem
• Set cover in sub-linear time

Cites work

• Approximation algorithms for combinatorial problems
• Candidate keys for relations
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• Logical definability of NP optimization problems
• On the approximation of shortest common supersequences and longest common subsequences
• On the hardness of approximating minimization problems
• On the ratio of optimal integral and fractional covers
• On the Structure of Armstrong Relations for Functional Dependencies
• Optimization, approximation, and complexity classes
• Polynomially bounded minimization problems which are hard to approximate

Cited in

(1)

• Targeted least cardinality candidate key for relational databases

This page was built for publication: Approximating minimum keys and optimal substructure screens

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