NDLI: Covering Things with Things

Content Provider	Springer Nature Link
Author	Langerman, Stefan Morin, Pat
Copyright Year	2004
Abstract	An abstract NP-hard covering problem is presented and fixed-parameter tractable algorithms for this problem are described. The running times of the algorithms are expressed in terms of three parameters: $n$ , the number of elements to be covered, $k$ , the number of sets allowed in the covering, and $d$ , the combinatorial dimension of the problem. The first algorithm is deterministic and has a running time of $O’(k^{dk}n)$ . The second algorithm is also deterministic and has a running time of $O’(k^{d(k+1)}+n^{d+1})$ . The third is a Monte-Carlo algorithm that runs in time $O’(\runtime)$ and is correct with probability $1-n^{-c}$ . Here, the $O’$ notation hides factors that are polynomial in $d$ . These algorithms lead to fixed-parameter tractable algorithms for many geometric and non-geometric covering problems.
Starting Page	717
Ending Page	729
Page Count	13
File Format	PDF
ISSN	01795376
Journal	Discrete & Computational Geometry
Volume Number	33
Issue Number	4
e-ISSN	14320444
Language	English
Publisher	Springer-Verlag
Publisher Date	2004-07-09
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Computational Mathematics and Numerical Analysis Combinatorics
Content Type	Text
Resource Type	Article
Subject	Discrete Mathematics and Combinatorics Theoretical Computer Science Computational Theory and Mathematics Geometry and Topology

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Covering Things with Things