An Efficient Streaming Algorithm for the Submodular Cover Problem

Abbas Bazzi, Ilija Bogunovic, Volkan Cevher, Marwa El Halabi, Ya-Ping Hsieh, Ashkan Norouzi Fard
2016
Article de conférence

Résumé

We initiate the study of the classical Submodular Cover (SC) problem in the data streaming model which we refer to as the Streaming Submodular Cover (SSC). We show that any single pass streaming algorithm using sublinear memory in the size of the stream will fail to provide any non-trivial approximation guarantees for SSC. Hence, we consider a relaxed version of SSC, where we only seek to find a partial cover. We design the first Efficient bicriteria Submodular Cover Streaming (ESC-Streaming) algorithm for this problem, and provide theoretical guarantees for its performance supported by numerical evidence. Our algorithm finds solutions that are competitive with the near-optimal offline greedy algorithm despite requiring only a single pass over the data stream. In our numerical experiments, we evaluate the performance of ESC-Streaming on active set selection and large- scale graph cover problems.

Official source

https://infoscience.epfl.ch/record/223493?ln=fr

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

Publications associées (30)

Distortion Optimized Multipath Video Streaming

Pascal Frossard, Dan Jurca

This paper addresses the problem of choosing the best streaming policy for distortion optimal multipath video delivery, under delay constraints. The streaming policy consists in a joint selection of the video packets to be transmitted, as well as their sending time, and the transmission path. A simple streaming model is introduced, which takes into account the video packet importance, and the dependencies among packets, and allows to compute the quality perceived by the receiver, as a function of the streaming policy. We derive an optimization problem based on the video abstraction model, under the assumption that the server knows the state of the network. A detailed analysis of the timing constraints in multipath video streaming provides helpful insights that lead to an efficient algorithm to solve the NP-hard policy optimization problem. We eventually propose a fast heuristic-based algorithm, that still provides close to optimal performance. Thanks to its limited complexity, this novel algorithm is finally implemented in live streaming scenarios, where it only induces a negligible distortion penalty compared to the optimal strategy. Simulation results finally show that the proposed scheduling solutions perform better than common scheduling algorithms, and represent very efficient strategies for both stored and live video streaming scenarios.

2004

Chargement

Packet Selection and Scheduling for Multipath Video Streaming

Pascal Frossard, Dan Jurca

This paper addresses the problem of choosing the best streaming policy for distortion optimal multipath video delivery, under delay constraints. The streaming policy consists in a joint selection of the video packets to be transmitted, as well as their sending time, and the transmission path. A simple streaming model is introduced, which takes into account the video packet importance, and the dependencies among packets, and allows to compute the quality perceived by the receiver, as a function of the streaming policy. We derive an optimization problem based on the video abstraction model, under the assumption that the server knows, or can predict the state of the network. A detailed analysis of the timing constraints in multipath video streaming provides helpful insights that lead to an efficient algorithm to solve the NP-hard streaming policy optimization problem. We eventually propose a fast heuristic-based algorithm, that still provides close to optimal performance. Thanks to its limited complexity, this novel algorithm is finally demonstrated in live streaming scenarios, where it only induces a negligible distortion penalty compared to an optimal strategy. Simulation results finally show that the proposed scheduling solutions perform better than common scheduling algorithms, and represent very efficient multipath streaming strategies for both stored and live video services.

2007

Chargement

We consider the problem of building a binary decision tree, to locate an object within a set by way of the least number of membership queries. This problem is equivalent to the “20 questions game” of information theory and is closely related to lossless source compression. If any query is admissible, Huffman coding is optimal with close to H[P] questions on average, the entropy of the prior distribution P over objects. However, in many realistic scenarios, there are constraints on which queries can be asked, and solving the problem optimally is NP-hard. We provide novel polynomial time approximation algorithms where constraints are defined in terms of “graph", general “cost", and “submodular" functions. In particular, we show that under graph constraints, there exists a constant approximation algorithm for locating the target in the set. We then extend our approach for scenarios where the constraints are defined in terms of general cost functions that depend only on the size of the query and provide an approxima- tion algorithm that can find the target within O(log(log n)) gap from the cost of the optimum algorithm. Submodular functions come as a natural generalization of cost functions with decreas- ing marginals. Under submodular set constraints, we devise an approximation algorithm that can find the target within O(log n) gap from the cost of the optimum algorithm. The proposed algorithms are greedy in a sense that at each step they select a query that most evenly splits the set without violating the underlying constraints. These results can be applied to network tomography, active learning and interactive content search.

2013

Chargement

Afficher plus