Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Theory of Computing Systems
Published in: Theory of Computing Systems 8/2018

18-01-2018

Set Cover Problems with Small Neighborhood Covers

Authors: Archita Agarwal, Venkatesan T. Chakaravarthy, Anamitra R. Choudhury, Sambudha Roy, Yogish Sabharwal

Published in: Theory of Computing Systems | Issue 8/2018

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this paper, we study a class of set cover problems that satisfy a special property which we call the small neighborhood cover property. This class encompasses several well-studied problems including vertex cover, interval cover, bag interval cover and tree cover. We design unified sequential, parallel and distributed algorithms that can handle any set cover problem falling under the above framework and yield constant factor approximations. The algorithms run in NC in the parallel setting and can be executed in polylogarithmic communication rounds in the distributed setting.
previous article Space Efficient Linear Time Algorithms for BFS, DFS and Applications
next article Parameterized Complexity of Voter Control in Multi-Peaked Elections

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Literature
1.
Agarwal, A., Chakaravarthy, V., Choudhury, A., Roy, S., Sabharwal, Y.: Distributed and parallel algorithms for set cover problems with small neighborhood covers. In: 33rd Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pp. 249–261 (2013)
2.
Bar-Noy, A., Bar-Yehuda, R., Freund, A., Naor, J., Schieber, B.: A unified approach to approximating resource allocation and scheduling. J. ACM 48(5), 1069–1090 (2001)MathSciNetCrossRefMATH
3.
Berman, P., DasGupta, B.: Improvements in throughout maximization for real-time scheduling. In: Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC), pp. 680–687 (2000)
4.
5.
Chakaravarthy, V., Kumar, A., Roy, S., Sabharwal, Y.: Resource allocation for covering time varying demands. In: Proceedings of the 19th European Symposium on Algorithms (ESA), pp. 543–554 (2011)
6.
Chakrabarty, D., Grant, E., Könemann, J.: On column-restricted and priority covering integer programs. In: 14th International Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 365–368 (2010)
7.
Dinur, I., Guruswami, V., Khot, S., Regev, O.: A new multilayered PCP and the hardness of hypergraph vertex cover. SIAM J. Comput. 34(5), 1129–1146 (2005)MathSciNetCrossRefMATH
8.
9.
Gandhi, R., Khuller, S., Srinivasan, A.: Approximation algorithms for partial covering problems. J. Algorithms 53(1), 55–84 (2004)MathSciNetCrossRefMATH
10.
Grandoni, F., Könemann, J., Panconesi, A.: Distributed weighted vertex cover via maximal matchings. ACM Transactions on Algorithms 5(1), 839–848 (2008)MathSciNetCrossRefMATH
11.
Khuller, S., Vishkin, U., Young, N.E.: A primal-dual parallel approximation technique applied to weighted set and vertex covers. J. Algorithms 17(2), 280–289 (1994)MathSciNetCrossRefMATH
12.
Koufogiannakis, C., Young, N.: Distributed algorithms for covering, packing and maximum weighted matching. Distrib. Comput. 24(1), 45–63 (2011)CrossRefMATH
13.
Kuhn, F., Moscibroda, T., Wattenhofer, R.: The price of being near-sighted. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 980–989 (2006)
14.
15.
16.
Panconesi, A., Sozio, M.: Fast primal-dual distributed algorithms for scheduling and matching problems. Distrib. Comput. 22(4), 269–283 (2010)CrossRefMATH
17.
Rajagopalan, S., Vazirani, V.: Primal-dual rnc approximation algorithms for set cover and covering integer programs. SIAM J. Comput. 28(2), 525–540 (1998)MathSciNetCrossRefMATH
18.
Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Proceedings of the 29th ACM Symposium on Theory of Computing (STOC), pp. 475–484 (1997)
19.
Williamson, D., Shmoys, D.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge (2011)CrossRefMATH
20.
Metadata
Title
Set Cover Problems with Small Neighborhood Covers
Authors
Archita Agarwal
Venkatesan T. Chakaravarthy
Anamitra R. Choudhury
Sambudha Roy
Yogish Sabharwal
Publication date
18-01-2018
Publisher
Springer US
Published in
Theory of Computing Systems / Issue 8/2018
Print ISSN: 1432-4350
Electronic ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-017-9842-1

Other articles of this Issue 8/2018

Theory of Computing Systems 8/2018 Go to the issue

OriginalPaper

Parameterized Complexity of Voter Control in Multi-Peaked Elections

OriginalPaper

Primitivity, Uniform Minimality, and State Complexity of Boolean Operations

OriginalPaper

Space Efficient Linear Time Algorithms for BFS, DFS and Applications

OriginalPaper

Polynomial Kernels for Vertex Cover Parameterized by Small Degree Modulators

OriginalPaper

Revisiting Connected Vertex Cover: FPT Algorithms and Lossy Kernels

OriginalPaper

Online Bin Packing with Advice of Small Size

Premium Partner

    Image Credits