Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

Search 250 million research papers

Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.

About 8,826 papers for “Set cover problem”

The Online Set Cover Problem

Noga Alon, Baruch Awerbuch, Yossi Azar et al. · SIAM Journal on Computing · 2009

Let $X=\{1,2,\ldots,n\}$ be a ground set of n elements, and let ${\cal S}$ be a family of subsets of X, $|{\cal S}|=m$, with a positive cost $c_S$ associated with each $S\in{\cal S}$. Consider the following online version of the set cover problem, described as a game between an algorithm and an adversary. An adversary gives elements to the algorithm from X one by one. Once a new element is given, the algorithm has to cover it by some set of ${\cal S}$ containing it. We assume that the elements of X and the members of ${\cal S}$ are known in advance to the algorithm; however, the set $X'\subseteq X$ of elements given by the adversary is not known in advance to the algorithm. (In general, $X'$ may be a strict subset of X.) The objective is to minimize the total cost of the sets chosen by the algorithm. Let ${\cal C}$ denote the family of sets in ${\cal S}$ that the algorithm chooses. At the end of the game the adversary also produces (offline) a family of sets ${\cal C}_{OPT}$ that covers $X'$. The performance of the algorithm is the ratio between the cost of ${\cal C}$ and the cost of ${\cal C}_{OPT}$. The maximum ratio, taken over all input sequences, is the competitive ratio of the algorithm. We present an $O(\log m\log n)$ competitive deterministic algorithm for the problem and establish a nearly matching $\Omega\bigl(\frac{\log n\log m}{\log\log m+\log\log n}\bigr)$ lower bound for all interesting values of m and n. The techniques used are motivated by similar techniques developed in computational learning theory for online prediction (e.g., the WINNOW algorithm) together with a novel way of converting a fractional solution into a deterministic online algorithm.

Cited by 123

A Note on: `Algorithms for Connected Set Cover Problem and Fault-Tolerant Connected Set Cover Problem'

Wei Ren, Qing Zhao · arXiv (Cornell University) · 2011

A flaw in the greedy approximation algorithm proposed by Zhang et al. for minimum connected set cover problem is corrected, and a stronger result on the approximation ratio of the modified greedy algorithm is established. The results are now consistent with the existing results on connected dominating set problem which is a special case of the minimum connected set cover problem.

Cited by 0Open access

The Online Set Cover Problem (Extended Abstract)

Noga Alon, Baruch Awerbuch, Yossi Azar et al. · 2008

Let X = {1, 2,..., n} be a ground set of n elements, and let S be a family of subsets of X, |S | = m, with a positive cost cS associated with each S ∈ S. Consider the following online version of the set cover problem, described as a game between an algorithm and an adversary. An adversary gives elements to the algorithm from X one-by-one. Once a new element is given, the algorithm has to cover it by some set of S containing it. We assume that the elements of X and the members of S are known in advance to the algorithm, however, the set X ′ ⊆ X of elements given by the adversary is not known in advance to the algorithm. (In general, X ′ may be a strict subset of X.) The objective is to minimize the total cost of the sets chosen by the algorithm. Let C denote the family of sets in S that the algorithm chooses. At the end of the game the adversary also produces (off-line) a family of sets COP T that covers X ′. The performance of the algorithm is the ratio between the cost of C and the cost of COP T. The maximum ratio, taken over all input sequences, is the competitive ratio of the algorithm. We present an O(log m � log n) competitive � deterministic algorithm for the problem, and estab-

Cited by 0

Cover Set Problem in Directional Sensor Networks

Yanli Cai, Wei Lou, Jianping Li · 2007

A directional sensor network consists of a number of directional sensors, which can switch to several directions to extend their sensing ability to cover the interested targets in a given area. Because a directional sensor has a smaller angle of sensing range or even does not cover any target when it is deployed, how to cover the interested targets becomes a major problem in directional sensor networks. In this paper, we address the directional cover set problem (DCS) of finding a cover set in a directional sensor network, in which the directions cover all the targets. We propose both centralized and distributed algorithms for the DCS. We also introduce two applications that utilize these algorithms to extend the network work time while maximizing the coverage of the targets. Simulation results are presented to demonstrate the performance of these algorithms and the applications.

Cited by 38

Private Approximation of the Set Cover Problem

Masatoshi Yashiro, Keisuke Tanaka, Masatoshi Yashiro et al. · 2006

Private approximation, introduced by Feigenbaum, Ishai, Malkin, Nissim, Strauss, and Wright, allows us to find approximate solutions with disclosing as little information as possible. In STOC 2006, Beimel, Carmi, Nissim, and Weinreb studied the private approximation for both the vertex cover and the max exact 3SAT problems. In this paper, we consider the set cover problem where the costs of all sets are polynomially bounded. We show that there exists neither a deterministic nor a randomized private approximation. We also consider the case that the frequencies of all elements are equal. We show that in this case there exist no deterministic private approximation.

Cited by 0

A Minimum Set-Cover Problem with several constraints

Jens Dörpinghaus, Carsten Düing, Vera Weil · Annals of Computer Science and Information Systems · 2019

A lot of problems in natural language processing can be interpreted using structures from discrete mathematics. In this paper we will discuss the search query and topic finding problem using a generic context-based approach. This problem can be described as a Minimum Set Cover Problem with several constraints. The goal is to find a minimum covering of documents with the given context for a fixed weight function. The aim of this problem reformulation is a deeper understanding of both the hierarchical problem using union and cut as well as the nonhierarchical problem using the union. We thus choose a modeling using bipartite graphs and suggest a novel reformulation using an integer linear program as well as novel graph-theoretic approaches.

Cited by 2Open access

Survey of Approximation Algorithms for Set Cover Problem

Himanshu Shekhar Dutta · 2009

In this thesis, I survey 11 approximation algorithms for unweighted set cover problem. I have also implemented the three algorithms and created a software library that stores the code I have written. The algorithms I survey are: 1. Johnson's standard greedy; 2. f-frequency greedy; 3. Goldsmidt, Hochbaum and Yu's modified greedy; 4. Halldorsson's local optimization; 5. Dur and Furer semi local optimization; 6. Asaf Levin's improvement to Dur and Furer; 7. Simple rounding; 8. Randomized rounding; 9. LP duality; 10. Primal-dual schema; and 11. Network flow technique. Most of the algorithms surveyed are refinements of standard greedy algorithm.

Cited by 8Open access

The multi-integer set cover and the facility terminal cover problem

2007

The facility terminal cover problem is a generalization of the vertex cover problem. The problem is to “cover ” the edges of an undirected graph G = (V, E) where each edge e is associated with a non-negative demand de. An edge e = [u, v] is covered if at least one of its endpoint vertices is allocated capacity of at least de. Each vertex v is associated with a non-negative weight wv. The goal is to allocate capacity cv ≥ 0 to each vertex v so that all edges are covered and the total allocation cost, � wvcv, is minimized. A recent paper by Xu, Yang and v∈V Xu (Networks, 50, (2007), 118-126), studied this problem, and presented a 2e- approximation algorithm for this problem for e the base of the natural logarithm. We generalize here the facility terminal cover problem to the multi-integer set cover, and relate that problem to the set cover problem, which it generalizes, and the multi-cover problem. We present a ∆-approximation algorithm for the multi-integer set cover problem, for ∆ the maximum coverage. This demonstrates that even though the multi-integer set cover problem generalizes the set cover problem, the same approximation ratio holds. In the special case of the facility terminal cover problem this yields a 2-approximation algorithm, and with run time dominated by the sorting of the edge demands. This approximation algorithm improves considerably on the result of Xu, Yang and Xu.

Cited by 0

Performance Evaluation of Vertex Cover and Set Cover Problem using Optimal Algorithm

B. M. Monjurul Alom, Mohammad Abdur Rouf · 2011

An appr oximation algorithm for a procedure that always provides some kind of solution, although it may fail to find the optimal solution. The approximate algorithms generally faster which can be proved to be close to the optimal solutions. The existing approximate algorithm for vertex cover and set cover problem is not optimal. To overcome this limitation, in this paper we have presented two new algorithms for vertex cover and set cover problem that provides the optimal solution that is better than approximate solution. The presented optimal algorithm and the existing well known approximation algorithm have almost the same time complexity but with respect to the solution our optimal algorithm outperforms compared to the existing approximation algorithm.

Cited by 6