Set Cover in Sub-linear Time
© Copyright 2018 by SIAM. We study the classic set cover problem from the perspective of sub-linear algorithms. Given access to a collection of m sets over n elements in the query model, we show that sub-linear algorithms derived from existing techniques have almost tight query complexities. On one...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Book |
| Language: | English |
| Published: |
Society for Industrial and Applied Mathematics
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137642 |