NDLI: Almost Optimal Streaming Algorithms for Coverage Problems

Please wait, while we are loading the content...

Beyond P vs. NP: Quadratic-Time Hardness for Big Data Problems

Randomized Composable Coresets for Matching and Vertex Cover

Asymptotically Optimal Approximation Algorithms for Coflow Scheduling

Bounding Laconic Proof Systems by Solving CSPs in Parallel

Some Sequential Algorithms are Almost Always Parallel

Distributed Partial Clustering

Is Our Model for Contention Resolution Wrong?: Confronting the Cost of Collisions

Concurrent Data Structures for Near-Memory Computing

Near Optimal Parallel Algorithms for Dynamic DFS in Undirected Graphs

Online Tree Caching

Almost Optimal Streaming Algorithms for Coverage Problems

Online Flexible Job Scheduling for Minimum Span

Matrix Multiplication, a Little Faster

Distributed Detection of Cycles

Optimal Reissue Policies for Reducing Tail Latency

Lower Bounds in the Asymmetric External Memory Model

Julienne: A Framework for Parallel Graph Algorithms using Work-efficient Bucketing

Provably Efficient Scheduling of Cache-oblivious Wavefront Algorithms

Bicriteria Distributed Submodular Maximization in a Few Rounds

Minimizing Total Weighted Flow Time with Calibrations

A Communication-Avoiding Parallel Algorithm for the Symmetric Eigenvalue Problem

Distributed Graph Clustering by Load Balancing

Impact of Knowledge on Election Time in Anonymous Networks

Hand-Over-Hand Transactions with Precise Memory Reclamation

Improved Cover Time Bounds for the Coalescing-Branching Random Walk on Graphs

Bounding Cache Miss Costs of Multithreaded Computations Under General Schedulers: Extended Abstract

On Energy Conservation in Data Centers

Tight Bounds for Clairvoyant Dynamic Bin Packing

Sharing is Caring: Multiprocessor Scheduling with a Sharable Resource

Fast Scheduling in Distributed Transactional Memory

Swarm-based Incast Congestion Control in Datacenters Serving Web Applications

Optimal Local Buffer Management for Information Gathering with Adversarial Traffic

The Mobile Server Problem

Brief Announcement: Meeting the Challenges of Parallelizing Sequential Programs

Brief Announcement: Scheduling Parallelizable Jobs Online to Maximize Throughput

Brief Announcement: Graph Matching in Massive Datasets

Brief Announcement: Approximation Algorithms for Unsplittable Resource Allocation Problems with Diseconomies of Scale

Brief Announcement: Parallel Dynamic Tree Contraction via Self-Adjusting Computation

Brief Announcement: Efficient Best Response Computation for Strategic Network Formation under Attack

Brief Announcement: Hazard Eras - Non-Blocking Memory Reclamation

Brief Announcement: A New Improved Bound for Coflow Scheduling

Brief Announcement: Using Multi-Level Parallelism and 2-3 Cuckoo Filters for Set Intersection Queries and Sparse Boolean Matrix Multiplication

Brief Announcement: Towards Fault-Tolerant Bin Packing for Online Cloud Resource Allocation

Brief Announcement: STAR (Space-Time Adaptive and Reductive) Algorithms for Dynamic Programming Recurrences with more than O(1) Dependency

Brief Announcement: Complete Visibility for Oblivious Robots in Linear Time

Brief Announcement: Extending Transactional Memory with Atomic Deferral

Brief Announcement: Hardware Transactional Storage Class Memory

Almost Optimal Streaming Algorithms for Coverage Problems

Content Provider	ACM Digital Library
Author	Esfandiari, Hossein Mirrokni, Vahab Bateni, MohammadHossein
Abstract	Maximum coverage and minimum set cover problems---here collectively called coverage problems---have been studied extensively in streaming models. However, previous research not only achieves suboptimal approximation factors and space complexities but also study a restricted set-arrival model which makes an explicit or implicit assumption on oracle access to the sets, ignoring the complexity of reading and storing the whole set at once. In this paper, we address the above shortcomings and present algorithms with improved approximation factor and improved space complexity, and prove that our results are almost tight. Moreover, unlike most of the previous work, our results hold in a more general edge-arrival model. More specifically, consider an instance with n sets, together covering m elements. Information arrives in the form of "edges" from sets to elements (denoting membership) in arbitrary order. We present (almost) optimal approximation algorithms for maximum coverage and minimum set cover problems in the streaming model with an (almost) optimal space complexity of Õ(n); i.e., the space is independent of the size of the sets or the size of the ground set of elements. These results not only improve the best known algorithms for the set-arrival model, but also are the first such algorithms for the more powerful edge-arrival model. In order to achieve the above results, we introduce a new general sketching technique for coverage functions: One can apply this sketching scheme to convert an α-approximation algorithm for a coverage problem to a (1-ε)α-approximation algorithm for the same problem in streaming model. We show the significance of our sketching technique by ruling out the possibility of solving coverage problems via accessing (as a black box) a (1 ± ε)-approximate oracle (e.g., a sketch function) that estimates the coverage function on any subfamily of the sets. Finally, we show that our streaming algorithms achieve an almost optimal space complexity.
Starting Page	13
Ending Page	23
Page Count	11
File Format	PDF
ISBN	9781450345934
DOI	10.1145/3087556.3087585
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2017-07-24
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Streaming algorithms Set cover Coverage maximization Distributed algorithm Submodular maximization
Content Type	Text
Resource Type	Article

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

Randomized Composable Core-sets for Distributed Submodular Maximization

Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints.

Bicriteria Distributed Submodular Maximization in a Few Rounds

Improved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid Constraints

Almost Optimal Streaming Algorithms for Coverage Problems

Streaming submodular maximization: massive data summarization on the fly

Deterministic algorithms for submodular maximization problems

Streaming Algorithms for Submodular Function Maximization (2015)

Online submodular welfare maximization: Greedy is optimal

Almost Optimal Streaming Algorithms for Coverage Problems

Similar Documents

Randomized Composable Core-sets for Distributed Submodular Maximization

Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints.

Bicriteria Distributed Submodular Maximization in a Few Rounds

Improved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid Constraints

Almost Optimal Streaming Algorithms for Coverage Problems

Streaming submodular maximization: massive data summarization on the fly

Deterministic algorithms for submodular maximization problems

Streaming Algorithms for Submodular Function Maximization (2015)

Online submodular welfare maximization: Greedy is optimal

Almost Optimal Streaming Algorithms for Coverage Problems