Kumar, Amit ;
Panda, Preeti R. ;
Sarangi, Smruti
Efficient online algorithm for maintaining kcover of sparse bitstrings
Abstract
We consider the online problem of representing a sparse bit string by a set of k intervals, where k is much smaller than the length of the string. The goal is to minimize the total length of these intervals under the condition that each 1bit must be in one of these intervals. We give an efficient greedy algorithm which takes time O(log k) per update (an update involves converting a 0bit to a 1bit), which is independent of the size of the entire string.
We prove that this greedy algorithm is 2competitive. We use
a natural linear programming relaxation for this problem, and analyze the algorithm by finding a dual feasible solution whose value matches the cost of the greedy algorithm.
BibTeX  Entry
@InProceedings{kumar_et_al:LIPIcs:2012:3863,
author = {Amit Kumar and Preeti R. Panda and Smruti Sarangi},
title = {{Efficient online algorithm for maintaining kcover of sparse bitstrings}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) },
pages = {249256},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897477},
ISSN = {18688969},
year = {2012},
volume = {18},
editor = {Deepak D'Souza and Telikepalli Kavitha and Jaikumar Radhakrishnan},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3863},
URN = {urn:nbn:de:0030drops38639},
doi = {http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2012.249},
annote = {Keywords: Online algorithms, string algorithms}
}
2012
Keywords: 

Online algorithms, string algorithms 
Seminar: 

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

Related Scholarly Article: 


Issue date: 

2012 
Date of publication: 

2012 