NDLI: On the random 2-stage minimum spanning tree

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

Dictionaries using variable-length keys and data, with applications

Inoculation strategies for victims of viruses and the sum-of-squares partition problem

On distance scales, embeddings, and efficient relaxations of the cut cone

The interface between computational and combinatorial geometry

Multiple-source shortest paths in planar graphs

Multidimensional balanced allocations

On levels in arrangements of surfaces in three dimensions

Isomorphism and embedding problems for infinite limits of scale-free graphs

Substring compression problems

A constant approximation algorithm for the one-warehouse multi-retailer problem

An O(VE) algorithm for ear decompositions of matching-covered graphs

LP decoding achieves capacity

Pianos are not flat: rigid motion planning in three dimensions

Loop quantum gravity

Approximation algorithms for cycle packing problems

Limitations of cross-monotonic cost sharing schemes

Distributed approaches to triangulation and embedding

Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality

The relative worst order ratio applied to paging

On hierarchical routing in doubling metrics

An optimal dynamic interval stabbing-max data structure?

A spectral heuristic for bisecting random graphs

Multicoloring unit disk graphs on triangular lattice points

Rigorous analysis of heuristics for NP-hard problems

An improved approximation algorithm for virtual private network design

The cover time of two classes of random graphs

Provably good moving least squares

Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group

Coins make quantum walks faster

Online ascending auctions for gradually expiring items

Lower bounds on the size of selection and rank indexes

Marriage, honesty, and stability

Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut

Computing the shortest path: A search meets graph theory

Online client-server load balancing without global information

Distributions of points in the unit-square and large k-gons

Adversarial deletion in a scale free random graph process

Optimizing markov models with applications to triangular connectivity coding

Sharing the cost more efficiently: improved approximation for multicommodity rent-or-buy

Popular matchings

Maximum-likelihood decoding of Reed-Solomon codes is NP-hard

A constant-factor approximation algorithm for optimal terrain guarding

Approximating the smallest k-edge connected spanning subgraph by LP-rounding

A group-strategyproof mechanism for Steiner forests

Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics

Dissections and trees, with applications to optimal mesh encoding and to random sampling

Strictly convex drawings of planar graphs

Fast convergence of selfish rerouting

Self-adjusting top trees

Complete partitions of graphs

An asymptotic approximation scheme for multigraph edge coloring

Network design for information networks

Coupling with the stationary distribution and improved sampling for colorings and independent sets

Manifold reconstruction from point samples

Matrix rounding with low error in small submatrices

Quantum algorithms for the triangle problem

Near-optimal online auctions

Dynamic dictionary matching and compressed suffix trees

Market equilibria for homothetic, quasi-concave utilities and economies of scale in production

The complexity of low-distortion embeddings between point sets

Finding large cycles in Hamiltonian graphs

Job shop scheduling with unit processing times

On geometric permutations induced by lines transversal through a fixed point

The influence of search engines on preferential attachment

Dotted interval graphs and high throughput genotyping

Online convex optimization in the bandit setting: gradient descent without a gradient

Dominator tree verification and vertex-disjoint paths

Collecting correlated information from a sensor network

Ray shooting amid balls, farthest point from a line, and range emptiness searching

Partial covering of hypergraphs

Collusion-resistant mechanisms for single-parameter agents

Sparse source-wise and pair-wise distance preservers

The expected value of random minimal length spanning tree of a complete graph

External-memory exact and approximate all-pairs shortest-paths in undirected graphs

Oblivious routing on node-capacitated and directed graphs

An optimal Bloom filter replacement

Two algorithms for general list matrix partitions

Computing minimal triangulations in time $O(n^{α}$ log n) = $o(n^{2.376})$

On the approximability of some network design problems

Sampling regular graphs and a peer-to-peer network

Delaunay triangulations approximate anchor hulls

Can the TPRI structure help us to solve the algebraic eigenproblem?

The hidden subgroup problem and permutation group theory

On profit-maximizing envy-free pricing

A categorization theorem on suffix arrays with applications to space efficient text indexes

On the polynomial time computation of equilibria for certain exchange economies

Approximation algorithms for low-distortion embeddings into low-dimensional spaces

Approximating connectivity augmentation problems

Approximating the average response time in broadcast scheduling

Subgradient and sampling algorithms for l1 regression

On the spread of viruses on the internet

Algorithms for combining rooted triplets into a galled phylogenetic network

Adaptivity and approximation for stochastic packing problems

Online topological ordering

Deterministic network coding by matrix completion

Space-time tradeoffs for approximate spherical range counting

Approximating vertex cover on dense graphs

A multiple-choice secretary algorithm with applications to online auctions

Lower bound for sparse Euclidean spanners

Girth restrictions for the 5-flow conjecture

Graph distances in the streaming model: the value of space

Distributed online call control on general networks

Efficient hashing with lookups in two memory accesses

How fast is the k-means method?

Finding the shortest bottleneck edge in a parametric minimum spanning tree

Approximating k-median with non-uniform capacities

The bin-covering technique for thresholding random geometric graph properties

Greedy optimal homotopy and homology generators

Optimal random number generation from a biased coin

Testing hierarchical systems

Improved recommendation systems

Towards a complete characterization of tries

Computing equilibria in multi-player games

A tight threshold for metric Ramsey phenomena

Primal-dual approach for directed vertex connectivity augmentation and generalizations

Improved schedule for radio broadcast

Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes

Analyzing and characterizing small-world graphs

Unknotting is in AM ∩ co-AM

Theory of semidefinite programming for sensor network localization

All maximal independent sets and dynamic dominance for sparse graphs

Network coding: does the model need tuning?

Online conflict-free coloring for intervals

Bidimensionality: new connections between FPT algorithms and PTASs

Rounds vs queries trade-off in noisy computation

New constructions of (α, β)-spanners and purely additive spanners

Linear equations, arithmetic progressions and hypergraph property testing

Lower bounds for external algebraic decision trees

An optimal online algorithm for packet scheduling with agreeable deadlines

Improved range-summable random variable construction algorithms

On approximating the depth and related problems

On the random 2-stage minimum spanning tree

Improved approximation for universal facility location

Random planar graphs with n nodes and a fixed number of edges

Controlled perturbation for Delaunay triangulations

A new look at survey propagation and its generalizations

Conformance testing in the presence of multiple faults

Selfish routing with atomic players

On the random 2-stage minimum spanning tree

Content Provider	ACM Digital Library
Author	Flaxman, Abraham D. Krivelevich, Michael Frieze, Alan
Abstract	It is known [7] that if the edge costs of the complete graph Kn are independent random variables, uniformly distributed between 0 and 1, then the expected cost of the minimum spanning tree is asymptotically equal to ζ(3) = Σ $^{∞}i=1$ i-3. Here we consider the following stochastic two-stage version of this optimization problem. There are two sets of edge costs cM: E ← R and cT: E ← R, called Monday's prices and Tuesday's prices, respectively. For each edge e, both costs cM(e) and cT(e) are independent random variables, uniformly distributed in [0, 1]. The Monday costs are revealed first. The algorithm has to decide on Monday for each edge e whether to buy it at Monday's price cM(e), or to wait until its Tuesday price cT(e) appears. The set of edges XM bought on Monday is then completed by the set of edges XT bought on Tuesday to form a spanning tree. If both Monday's and Tuesday's prices were revealed simultaneously, then the optimal solution would have expected cost ζ(3)/2 + o(1). We show that in the case of two-stage optimization, the expected value of the optimal cost exceeds ζ(3)/2 by an absolute constant ∈ > 0. We also consider a threshold heuristic, where the algorithm buys on Monday only edges of cost less than α and completes them on Tuesday in an optimal way, and show that the optimal choice for α is α = 1/n with the expected cost ζ(3) - 1/2 + o(1). The threshold heuristic is shown to be sub-optimal. Finally we discuss the directed version of the problem, where the task is to construct a spanning out-arborescence rooted at a fixed vertex r, and show, somewhat surprisingly, that in this case a simple variant of the threshold heuristic gives the asymptotically optimal value 1 - 1/e + o(1).
Starting Page	919
Ending Page	926
Page Count	8
File Format	PDF
ISBN	0898715857
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2005-01-23
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