[go: up one dir, main page]

Meyerson et al., 2008 - Google Patents

Cost-distance: Two metric network design

Meyerson et al., 2008

View PDF
Document ID
7512988065436652970
Author
Meyerson A
Munagala K
Plotkin S
Publication year
Publication venue
SIAM Journal on Computing

External Links

Snippet

We present the Cost-Distance problem: finding a Steiner tree which optimizes the sum of edge costs along one metric and the sum of source-sink distances along an unrelated second metric. We give the first known O(\logk) randomized approximation scheme for Cost …
Continue reading at www.researchgate.net (PDF) (other versions)

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/12—Shortest path evaluation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L41/00—Arrangements for maintenance or administration or management of packet switching networks
    • H04L41/50—Network service management, i.e. ensuring proper service fulfillment according to an agreement or contract between two parties, e.g. between an IT-provider and a customer
    • H04L41/5041—Service implementation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/02—Topology update or discovery
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/48—Routing tree calculation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L41/00—Arrangements for maintenance or administration or management of packet switching networks
    • H04L41/12—Arrangements for maintenance or administration or management of packet switching networks network topology discovery or management
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/66—Arrangements for connecting between networks having differing types of switching systems, e.g. gateways
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/14—Routing performance; Theoretical aspects
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/30—Special provisions for routing multiclass traffic
    • H04L45/306—Route determination based on the nature of the carried application
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/04—Interdomain routing, e.g. hierarchical routing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/30—Special provisions for routing multiclass traffic
    • H04L45/302—Route determination based on requested QoS
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L41/00—Arrangements for maintenance or administration or management of packet switching networks
    • H04L41/08—Configuration management of network or network elements
    • H04L41/0803—Configuration setting of network or network elements
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/28—Data switching networks characterised by path configuration, e.g. local area networks [LAN], wide area networks [WAN]

Similar Documents

Publication Publication Date Title
Meyerson et al. Cost-distance: Two metric network design
Chekuri et al. Approximation algorithms for nonuniform buy-at-bulk network design
Gupta et al. Simpler and better approximation algorithms for network design
Raghavendra Optimal algorithms and inapproximability results for every CSP?
Goel et al. On the communication and streaming complexity of maximum bipartite matching
Van Mieghem et al. Hop-by-hop quality of service routing
Karakostas Faster approximation schemes for fractional multicommodity flow problems
Ljubić et al. Exact approaches to the single‐source network loading problem
Robinius et al. Robust optimal discrete arc sizing for tree-shaped potential networks
Santos et al. Shortest path finding in quantum networks with quasi-linear complexity
Mosk-Aoyama et al. Fully distributed algorithms for convex optimization problems
Van Zuylen Deterministic sampling algorithms for network design
Guha et al. A constant factor approximation for the single sink edge installation problem
Hurkens et al. Virtual private network design: A proof of the tree routing conjecture on ring networks
Zheng Adaptation of network simplex for the traffic assignment problem
Jothi et al. Improved approximation algorithms for the single-sink buy-at-bulk network design problems
Grandoni et al. From uncertainty to nonlinearity: Solving virtual private network via single-sink buy-at-bulk
Palod et al. Reliability-based optimization of water distribution networks
Williamson et al. A simpler and better derandomization of an approximation algorithm for single source rent-or-buy
Mosk-Aoyama et al. Fully distributed algorithms for convex optimization problems
Gupta et al. A constant-factor approximation for stochastic Steiner forest
Feng et al. A fast hybrid ε-approximation algorithm for computing constrained shortest paths
US20130279327A1 (en) Locating Traffic Reduction Utilities in Communication Networks
Goel et al. An oblivious O (1)-approximation for single source buy-at-bulk
Angelopoulos A near-tight bound for the online steiner tree problem in graphs of bounded asymmetry