Automated category tree construction: hardness bounds and algorithms
DOI10.1145/3664283zbMATH Open1541.68286MaRDI QIDQ6572611
Tova Milo, Uri Avron, Ido Guy, Slava Novgorodov, Shay Gershtein
Publication date: 15 July 2024
Published in: ACM Transactions on Database Systems (Search for Journal in Brave)
approximation algorithmsmaximum independent settaxonomy constructionapproximation hardness boundscategory tree construction
Database theory (68P15) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Data structures (68P05) Approximation algorithms (68W25)
Cites Work
- SDP-based algorithms for maximum independent set problems on hypergraphs
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Improved lower bounds on k‐independence
- UG-hardness to NP-hardness by losing half
- Exactly Solving the Maximum Weight Independent Set Problem on Large Real-World Graphs
- Probability and Computing
- Data Mining and Knowledge Discovery Handbook
- Unnamed Item
This page was built for publication: Automated category tree construction: hardness bounds and algorithms
