NDLI: Online Metric Tracking and Smoothing

Content Provider	Springer Nature Link
Author	Chen, Sixia Russell, Alexander
Copyright Year	2012
Abstract	We consider the online smoothing problem, in which a tracker is required to maintain distance no more than Δ≥0 from a time-varying signal f while minimizing its own movement. The problem is determined by a metric space (X,d) with an associated cost function c:ℝ→ℝ. Given a signal f 1,f 2,…∈X the tracker is responsible for producing a sequence a 1,a 2,… of elements of X that meet the proximity constraint: d(f i ,a i )≤Δ. To complicate matters, the tracker is on-line—the value a i may only depend on f 1,…,f i —and wishes to minimize the cost of his travels, ∑c(d(a i ,a i+1)). We evaluate such tracking algorithms competitively, comparing this with the cost achieved by an optimal adversary apprised of the entire signal in advance.The problem was originally proposed by Yi and Zhang (In: Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms (SODA), pp. 1098–1107. ACM Press, New York, 2009), who considered the natural circumstance where the metric spaces are taken to be ℤ k with the ℓ 2 metric and the cost function is equal to 1 unless the distance is zero (thus the tracker pays a fixed cost for any nonzero motion). We begin by studying arbitrary metric spaces with the “pay if you move” metric of Yi and Zhang (In: Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms (SODA), pp. 1098–1107. ACM Press, New York, [2009]) described above and describe a natural randomized algorithm that achieves a O(logb Δ)-competitive ratio, where b Δ=max x∈X \|B Δ(x)\| is the maximum number of points appearing in any ball of radius Δ. We show that this bound is tight. We then focus on the metric space ℤ with natural families of monotone cost functions c(x)=x p for some p≥0. We consider both the expansive case (p≥1) and the contractive case (p<1), and show that the natural lazy algorithm performs well in the expansive case. In the contractive case, we introduce and analyze a novel deterministic algorithm that achieves a constant competitive ratio depending only on p. Finally, we observe that by slightly relaxing the guarantee provided by the tracker, one can obtain natural analogues of these algorithms that work in continuous metric spaces.
Starting Page	133
Ending Page	151
Page Count	19
File Format	PDF
ISSN	01784617
Journal	Algorithmica
Volume Number	68
Issue Number	1
e-ISSN	14320541
Language	English
Publisher	Springer US
Publisher Date	2012-06-28
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Online algorithms Randomized algorithms Algorithm Analysis and Problem Complexity Theory of Computation Mathematics of Computing Algorithms Computer Systems Organization and Communication Networks Data Structures, Cryptology and Information Theory
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computer Science Applications

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

Online Randomized Multiprocessor Scheduling

A Randomized O(log2 k)-Competitive Algorithm for Metric Bipartite Matching

An Improved Algorithm for Online Unit Clustering

Communication Complexity of Quasirandom Rumor Spreading

On the Competitive Ratio for Online Facility Location

Randomized quickhull

Online Bin Packing with Advice

Online File Caching with Rejection Penalties

Online Unweighted Knapsack Problem with Removal Cost

Online Metric Tracking and Smoothing

Similar Documents

Online Randomized Multiprocessor Scheduling

A Randomized O(log2 k)-Competitive Algorithm for Metric Bipartite Matching

An Improved Algorithm for Online Unit Clustering

Communication Complexity of Quasirandom Rumor Spreading

On the Competitive Ratio for Online Facility Location

Randomized quickhull

Online Bin Packing with Advice

Online File Caching with Rejection Penalties

Online Unweighted Knapsack Problem with Removal Cost

Online Metric Tracking and Smoothing