We give the first nontrivial approximation algorithms for Steiner tree problem and generalized network on general directed graphs. These problems have several applications in design multicast routing. For both problems, best ratios known before our work were trivial O(k)-approximations. problem, we a family of that achieves an ratio i(i − 1)k1/i time O(nik2i) any fixed i > 1, where k is number terminals. Thus, O(kϵ) can be achieved polynomial ϵ 0. Setting = log k, obtain O(log2 k)...

Are we as a society getting more polarized, and if so, why? We try to answer this question through model of opinion formation. Empirical studies have shown that homophily results in polarization. However, show DeGroot's well-known formation based on repeated averaging can never be polarizing, even individuals are arbitrarily homophilous. generalize account for phenomenon social psychology biased assimilation: when presented with mixed or inconclusive evidence complex issue, draw undue...

Wireless sensor networks (WSNs) are emerging as an effective means for environment monitoring. This paper investigates a strategy energy efficient monitoring in WSNs that partitions the sensors into covers, and then activates covers iteratively round-robin fashion. approach takes advantage of overlap created when many monitor single area. Our work builds upon previous [13], where model is first formulated. We have designed three approximation algorithms variation SET K-COVER problem,...

We present a truthful auction for pricing advertising slots on web-page assuming that advertisements different merchants must be ranked in decreasing order of their (weighted) bids. This captures both the Overture model where bidders are submitted bids, and Google expected revenue (or utility) advertisement generates. Assuming separable click-through rates, we prove revenue-equivalence between our non-truthful next-price auctions currently use.

In this paper, we analyze the efficiency of Monte Carlo methods for incremental computation PageRank, personalized and similar random walk based (with focus on SALSA), large-scale dynamically evolving social networks. We assume that graph friendships is stored in distributed shared memory, as case large networks such Twitter. For global network has n nodes, m adversarially chosen edges arrive a order. show with reset probability ε, expected total work needed to maintain an accurate estimate...

The Internet is facing two problems simultaneously: there a need for faster switching/routing infrastructure and to introduce guaranteed qualities-of-service (QoS). Each problem can be solved independently: switches routers made by using input-queued crossbars instead of shared memory systems; QoS provided weighted-fair queueing (WFQ)-based packet scheduling. Until now, however, the solutions have been mutually exclusive-all work on WFQ-based scheduling algorithms has required that...

Medium access techniques for wireless sensor networks raise the important question of providing periodic energy-efficient radio sleep cycles while minimizing end-to-end communication delays. This study aims to minimize latency given that each has a duty cycling requirement being awake only 1/k time slots on an average. As first step we consider single wake-up schedule case, where can choose exactly one k wake up. We formulate novel graph-theoretical abstraction this problem in general...

The Internet is facing two problems simultaneously: there a need for faster switching/routing infrastructure, and to introduce guaranteed qualities of service (QoS). Each problem can be solved independently: switches routers made by using input-queued crossbars, instead shared memory systems; QoS provided WFQ-based packet scheduling. However, until now, the solutions have been mutually exclusive-all work on scheduling algorithms has required that switches/routers use output-queueing, or...

Internet routers require buffers to hold pack- ets during times of congestion. The need be fast, and so ideally they should small enough use fast memory technologies such as SRAM or all-optical buffering. Unfortunately, a widely used rule-of-thumb says we bandwidth-delay product buffering at each router not lose link utilization. This can prohibitively large. In recent paper, Appenzeller et al. challenged this showed that for backbone network, the buffer size divided by √ N without...

Consider the following communication problem. Alice holds a graph GA = (P,Q,EA) and Bob GB (P,Q,EB), where |P| |Q| n. is allowed to send message m that depends only on GA. must then output matching M ⊆ EA ∪ EB. What minimum size of sends allows recover at least (1 − e) times maximum in GB? The length one-round complexity approximating bipartite matching. It easy see also gives lower bound space needed by one-pass streaming algorithm compute e)-approximate focus this work understand In...

We address the question of aggregating preferences voters in context participatory budgeting. scrutinize voting method currently used practice, underline its drawbacks, and introduce a novel scheme tailored to this setting, which we call “Knapsack Voting.” study strategic properties—we show that it is strategy-proof under natural model utility (a dis-utility given by ℓ 1 distance between outcome true preference voter) “partially” general additive utilities. extend Knapsack Voting more...

We present new algorithms for Personalized PageRank estimation and search. First, the problem of estimating (PPR) from a source distribution to target node, we bidirectional estimator with simple yet strong guarantees on correctness performance, 3x 8x speedup over existing estimators in experiments diverse set networks. Moreover, it has clean algebraic structure which enables be used as primitive Search problem: Given network like Facebook, query "people named John", searching user, return...

We propose a new algorithm, FAST-PPR, for computing personalized PageRank: given start node s and target t in directed graph, threshold δ, it computes the Personalized PageRank π_s(t) from to t, guaranteeing that relative error is small as long πs(t) > δ. Existing algorithms this problem have running-time of Ω(1/δ comparison, FAST-PPR has provable average guarantee O(√d/δ) (where d in-degree graph). This significant improvement, since δ often O(1/n) n number nodes) applications. also...

Y. Bartal (1996, 1998) gave a randomized polynomial time algorithm that given any n point metric G, constructs tree T such the expected stretch (distortion) of edge is at most O (log log n). His result has found several applications and in particular resulted approximation algorithms for many graph optimization problems. However based on his are inherently randomized. In this paper we derandomize use Bartal's design algorithms. We give an efficient finite O(n n) trees probability...

Internet routers require buffers to hold packets during times of congestion. The need be fast, and so ideally they should small enough use fast memory technologies such as SRAM or all-optical buffering. Unfortunately, a widely used rule-of-thumb says we bandwidth-delay product buffering at each router not lose link utilization. This can prohibitively large. In recent paper, Appenzeller et al. challenged this showed that for backbone network, the buffer size divided by pN without sacrificing...

Article Rounding via trees: deterministic approximation algorithms for group Steiner trees and k-median Share on Authors: Moses Charikar Computer Science Department, Stanford University UniversityView Profile , Chandra Chekuri Ashish Goel Sudipto Guha Authors Info & Claims STOC '98: Proceedings of the thirtieth annual ACM symposium Theory computingMay 1998 Pages 114–123https://doi.org/10.1145/276698.276719Online:23 May 1998Publication History 96citation795DownloadsMetricsTotal...

We consider the problem of finding efficient trees to send information from k sources a single sink in network where can be aggregated at intermediate nodes tree. Specifically, we assume that if j is traveling over link, total needs transmitted f(j). One natural and important (though not necessarily comprehensive) class functions those which are concave, non-decreasing, satisfy f(0) = 0. Our goal find tree good approximation simultaneously optimum for all such functions. This motivated by...

Efficient data retrieval in a peer-to-peer system like Freenet is challenging problem. We study the impact of cache replacement policy on performance Freenet. find that, with Freenet's LRU (least recently used) replacement, there steep reduction hit ratio increasing load. Based intuition from small-world models and recent theoretical results by Kleinberg, we propose an enhanced-clustering scheme for use place LRU. Such forces routing tables to resemble neighbor relationships acquaintance...

Spin-torque transfer magnetic RAM (STT MRAM) is a promising candidate for future embedded applications. It combines the desirable attributes of current memory technologies such as SRAM, DRAM, and flash memories (fast access time, low cost, high density, non-volatility). also solves critical drawbacks conventional MRAM technology: poor scalability write current. However, variations in process parameters can lead to large number cells fail, severely affecting yield array. In this paper, we...

We propose and analyze two algorithms for maintaining approximate Personalized PageRank (PPR) vectors on a dynamic graph, where edges are added or deleted. Our natural versions of known local variations power iteration. One, Forward Push, propagates probability mass forwards along from source node, while the other, Reverse changes backwards target. In both variations, we maintain an invariant between vectors, when edge is updated, our algorithm first modifies to restore invariant, then...

Understanding the impact of technology use on business-to-business (B2B) sales profession has been one priorities for scholars over 20 years. While extant literature focused mainly stand-alone technologies like customer relationship management and social media, few studies have taken a holistic approach to understand how transformed function corresponding this change had salesperson organizational level. Employing morphological analysis (MA), we conduct an extensive review last two decades...

We obtain the first non-trivial approximation algorithms for Steiner Tree problem and Generalized in general directed graphs. Essentially no were known these problems. For Directed problem, we design a family of which achieve an ratio O(k^\epsilon) time O(kn^{1/\epsilon}) any fixed (\epsilon < 0), where k is number terminals to be connected. Problem, give algorithm achieves O(k^{2/3}\log^{1/3} k), pairs Related problems including Group tree Node Weighted several others can reduced preserving...