Derandomization for sparse approximations and independent sets

DOI10.1007/3-540-60246-1_126zbMATH Open1193.68133OpenAlexW1597384236MaRDI QIDQ3569012FDOQ3569012

Authors: Thomas Hofmeister, Hanno Lefmann 

Publication date: 17 June 2010

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

Full work available at URL: https://doi.org/10.1007/3-540-60246-1_126

Recommendations

• Computing sparse approximations deterministically
• Multiplying Pessimistic Estimators: Deterministic Approximation of Max TSP and Maximum Triangle Packing
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• Deterministic approximation algorithms for the maximum traveling salesman and maximum triangle packing problems
• scientific article; zbMATH DE number 1163722

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cited In (4)

• Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• Pipage rounding, pessimistic estimators and matrix concentration
• Verifiable Obtained Random Subsets for Improving SPHINCS+

This page was built for publication: Derandomization for sparse approximations and independent sets

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