NDLI: Linked decompositions of networks and the power of choice in Polya urns

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

Fast dimension reduction using Rademacher series on dual BCH codes

Estimators and tail bounds for dimension reduction in lα (0 < α ≤ 2) using stable random projections

A deterministic sub-linear time sparse fourier algorithm via non-adaptive compressed sensing methods

Explicit constructions for compressed sensing of sparse signals

Improved distance sensitivity oracles via random sampling

Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization

Holographic algorithms with unsymmetric signatures

The UGC hardness threshold of the $ℓ_{p}$ Grothendieck problem

Succinct approximate convex pareto curves

Efficient reductions among lattice problems

Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles

Greedy drawings of triangulations

Maintaining deforming surface meshes

Exact and efficient 2D-arrangements of arbitrary algebraic curves

On properties of random dissections and triangulations

Graph algorithms for biological systems analysis

Adaptive local ratio

Two-phase greedy algorithms for some classes of combinatorial linear programs

Analysis of greedy approximations with nonsubmodular potential functions

Yet another algorithm for dense max cut: go greedy

Computing large matchings fast

A fractional model of the border gateway protocol (BGP)

Minimizing average latency in oblivious routing

Distributed broadcast in unknown radio networks

The power of memory in randomized broadcasting

Competitive queue management for latency sensitive packets

Rapid mixing of Gibbs sampling on graphs that are sparse on average

Product growth and mixing in finite groups

Concatenated codes can achieve list-decoding capacity

Noisy sorting without resampling

Algorithms for the coalitional manipulation problem

On allocations that maximize fairness

On the value of coordination in network design

Auctions for structured procurement

Fast load balancing via bounded best response

(Almost) optimal coordination mechanisms for unrelated machine scheduling

Ultra-low-dimensional embeddings for doubling metrics

Earth mover distance over high-dimensional spaces

Almost Euclidean subspaces of $ℓ^{N}_{1}$ via expander codes

Embedding metric spaces in their intrinsic dimension

Optimal universal graphs with deterministic embedding

Fast and reliable reconstruction of phylogenetic trees with very short edges

Trace reconstruction with constant deletion probability and related results

Improved string reconstruction over insertion-deletion channels

Dimension augmentation and combinatorial criteria for efficient error-resistant DNA self-assembly

Approximating general metric distances between a pattern and a text

A near-linear time algorithm for computing replacement paths in planar directed graphs

Bounded-leg distance and reachability oracles

A nearly linear time algorithm for the half integral disjoint paths packing

Fast edge splitting and Edmonds' arborescence construction for unweighted graphs

Nondecreasing paths in a weighted graph or: how to optimally read a train schedule

Broadcast scheduling: algorithms and complexity

Graph balancing: a special case of scheduling unrelated parallel machines

Non-clairvoyant scheduling with precedence constraints

Provably good multicore cache performance for divide-and-conquer algorithms

Balls and bins with structure: balanced allocations on hypergraphs

Arc-disjoint in-trees in directed graphs

Finding one tight cycle

Set connectivity problems in undirected graphs and the directed Steiner network problem

Matroid intersection, pointer chasing, and Young's seminormal representation of $S_{n}$

Iterated rounding algorithms for the smallest k-edge connected spanning subgraph

Shuffling cards, adding numbers, and symmetric functions

On the bichromatic k-set problem

Geodesic Delaunay triangulation and witness complex in the plane

Minimum weight convex Steiner partitions

Improved algorithms for fully dynamic geometric spanners and geometric routing

On the connectivity of dynamic random geometric graphs

Improved algorithmic versions of the Lovász Local Lemma

L(2,1)-labelling of graphs

Catalan structures and dynamic programming in H-minor-free graphs

Computing excluded minors

An algorithm for improving graph partitions

Improved algorithms for orienteering and related problems

Approximation algorithms for labeling hierarchical taxonomies

Fast approximation of the permanent for very dense problems

Approximating TSP on metrics with bounded global growth

Fully polynomial time approximation schemes for stochastic dynamic programs

On distributing symmetric streaming computations

Tight lower bounds for selection in randomly ordered streams

On distance to monotonicity and longest increasing subsequence of a data stream

Declaring independence via the sketching of sketches

Why simple hash functions work: exploiting the entropy in a data stream

Maximum overhang

Deterministic random walks on regular trees

Quasirandom rumor spreading

Universality of random graphs

The effect of induced subgraphs on quasi-randomness

Clustering for metric and non-metric distance measures

Metric clustering via consistent labeling

On clustering to minimize the sum of radii

A constant factor approximation algorithm for k-median clustering with outliers

Geometric clustering: fixed-parameter tractability and lower bounds with respect to the dimension

The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond

Designing networks with good equilibria

Ascending auctions for integral (poly)matroids with concave nondecreasing separable values

Fast algorithms for finding proper strategies in game trees

Incentive compatible regression learning

Space-efficient dynamic orthogonal point location, segment intersection, and range reporting

In-place 2-d nearest neighbor search

Distribution-sensitive point location in convex subdivisions

Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm

Sampling algorithms and coresets for $ℓ_{p}$ regression

Stochastic analyses for online combinatorial optimization problems

Online make-to-order joint replenishment model: primal dual competitive algorithms

Parallel monotonicity reconstruction

Better bounds for online load balancing on unrelated machines

Online budgeted matching in random input models with applications to Adwords

Computational advertising

Linked decompositions of networks and the power of choice in Polya urns

A local algorithm for finding dense subgraphs

PageRank and the random surfer model

Charity auctions on social networks

On the approximability of influence in social networks

Fast asynchronous byzantine agreement and leader election with full information

Unconditionally reliable message transmission in directed networks

A tight lower bound for parity in noisy communication networks

Ranged hash functions and the price of churn

Algorithms for distributed functional monitoring

Real-time indexing over fixed finite alphabets

Finding an optimal tree searching strategy in linear time

Dynamic optimality for skip lists and B-trees

Splay trees, Davenport-Schinzel sequences, and the deque conjecture

Fully dynamic algorithm for graph spanners with poly-logarithmic update time

SPREAD: an adaptive scheme for redundant and fair storage in dynamic heterogeneous storage systems

Price based protocols for fair resource allocation: convergence time analysis and extension to Leontief utilities

Lower-bounded facility location

A plant location guide for the unsure

Approximating connected facility location problems via random facility sampling and core detouring

The hiring problem and Lake Wobegon strategies

Weak ε-nets and interval chains

Robust cost colorings

Comparing the strength of query types in property testing: the case of testing k-colorability

Sampling stable marriages: why spouse-swapping won't work

On stars and Steiner stars

Cutting cycles of rods in space: hardness and approximation

Empty-ellipse graphs

Recognizing partial cubes in quadratic time

Approximating geometric coverage problems

Linked decompositions of networks and the power of choice in Polya urns

Content Provider	ACM Digital Library
Author	Amanatidis, Christos Lin, Henry Karp, Richard M. Papadimitriou, Christos H. Sideri, Martha
Abstract	A linked decomposition of a graph with n nodes is a set of subgraphs covering the n nodes such that all pairs of subgraphs intersect; we seek linked decompositions such that all subgraphs have about √n vertices, logarithmic diameter, and each vertex of the graph belongs to either one or two subgraphs. A linked decomposition enables many control and management functions to be implemented locally, such as resource sharing, maintenance of distributed directory structures, deadlock-free routing, failure recovery and load balancing, without requiring any node to maintain information about the state of the network outside the subgraphs to which it belongs. Linked decompositions also enable efficient routing, schemes with small routing tables, which we describe in Section 5. Our main contribution is to show that "Internet-like graphs" (e.g. the preferential attachment model proposed by Barabasi et al. [10] and other similar models) have linked decompositions with the parameters described above with high probability; moreover, our experiments show that the Internet topology itself can be so decomposed. Our proof proceeds by analyzing a novel process, which we call Polya urns with the power of choice, which may be of great independent interest. In this new process, we start with n nonempty bins containing O(n) balls total, and each arriving ball is placed in the least loaded of m bins, drawn independently at random with probability proportional to load. Our analysis shows that in our new process, with high probability the bin loads become roughly balanced some time before $O(n^{2+ε})$ further balls have arrived and stay roughly balanced, regardless of how the initial O(n) balls were distributed, where ε > 0 can be arbitrarily small, provided m is large enough.
Starting Page	993
Ending Page	1002
Page Count	10
File Format	PDF
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2008-01-20
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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