Loading...
Please wait, while we are loading the content...
Similar Documents
Partial Information Spreading with Application to Distributed Maximum Coverage (2010)
| Content Provider | CiteSeerX |
|---|---|
| Author | Shachnai, Hadas Hillel, Keren Censor |
| Abstract | This paper addresses partial information spreading among n nodes of a network. As opposed to traditional information spreading, where each node has a message that must be received by all nodes, we propose a relaxed requirement, where only n/c nodes need to receive each message, and every node should receive n/c messages, for some c ≥ 1. As a key tool in our study we introduce the novel concept of weak conductance, a generalization of classic graph conductance which allows to analyze the time required for partial information spreading. We show the power of weak conductance as a measure of how well-knit the components of a graph are, by giving an example of a graph family for which the conductance is O(n −2), while the weak conductance is as large as 1/2. For such graphs, weak conductance can be used to show that partial information spreading requires time complexity of O(log n). Finally, we demonstrate the usefulness of partial information spreading in solving the maximum coverage problem, which naturally arises in circuit layout, job scheduling and facility location, as well as in distributed resource allocation with a global budget constraint. Our algorithm yields a constant approximation factor and a constant deviation from the given budget. For graphs with a constant weak conductance, this implies a scalable time complexity for solving a problem with a global constraint. |
| File Format | |
| Publisher Date | 2010-01-01 |
| Access Restriction | Open |
| Subject Keyword | Global Budget Constraint Maximum Coverage Problem Traditional Information Spreading Classic Graph Conductance Weak Conductance Distributed Resource Allocation Constant Approximation Factor Novel Concept Constant Weak Conductance Graph Family Circuit Layout Partial Information Key Tool Global Constraint Distributed Maximum Coverage Algorithm Yield Facility Location Time Complexity Relaxed Requirement Partial Information Spreading Job Scheduling Scalable Time Complexity Constant Deviation |
| Content Type | Text |
| Resource Type | Article |
