NDLI: Path decomposition under a new cost measure with applications to optical network design

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

ACM Transactions on Algorithms (TALG) : Volume 13

ACM Transactions on Algorithms (TALG) : Volume 12

ACM Transactions on Algorithms (TALG) : Volume 11

ACM Transactions on Algorithms (TALG) : Volume 10

ACM Transactions on Algorithms (TALG) : Volume 9

ACM Transactions on Algorithms (TALG) : Volume 8

ACM Transactions on Algorithms (TALG) : Volume 7

ACM Transactions on Algorithms (TALG) : Volume 6

ACM Transactions on Algorithms (TALG) : Volume 5

ACM Transactions on Algorithms (TALG) : Volume 4

Uniform deterministic dictionaries

No sorting? better searching!

Thin heaps, thick heaps

Alternation and redundancy analysis of the intersection problem

Randomized minimum spanning tree algorithms using exponentially fewer random bits

A faster and simpler fully dynamic transitive closure

Finding a long directed cycle

Rectangular layouts and contact graphs

The priority R-tree: A practically efficient and worst-case optimal R-tree

Approximate distance oracles for geometric spanners

Improved bounds for scheduling conflicting jobs with minsum criteria

The collective memory of amnesic processes

Faster approximation schemes for fractional multicommodity flow problems

Hierarchical bin buffering: Online local moments for dynamic external memory arrays

Path decomposition under a new cost measure with applications to optical network design

ACM Transactions on Algorithms (TALG) : Volume 3

ACM Transactions on Algorithms (TALG) : Volume 2

ACM Transactions on Algorithms (TALG) : Volume 1

Path decomposition under a new cost measure with applications to optical network design

Content Provider	ACM Digital Library
Author	Zhang, Lisa Anshelevich, Elliot
Copyright Year	2008
Abstract	We introduce a problem directly inspired by its application to DWDM (dense wavelength division multiplexing) network design. We are given a set of demands to be carried over a network. Our goal is to choose a route for each demand and to decompose the network into a collection of edge-disjoint simple paths. These paths are called optical line systems. The cost of routing one unit of demand is the number of line systems with which the demand route overlaps; our design objective is to minimize the total cost over all demands. This cost metric is motivated by the need to minimize O-E-O $(\textit{optical-electrical-optical})$ conversions in optical transmission. For given line systems, it is easy to find the optimal demand routes. On the other hand, for given demand routes designing the optimal line systems can be NP-hard. We first present a 2-approximation for general network topologies. As optical networks often have low node degrees, we offer an algorithm that finds the optimal solution for the special case in which the node degree is at most 3. Our solution is based on a local greedy approach. If neither demand routes nor line systems are fixed, the situation becomes much harder. Even for a restricted scenario on a 3-regular Hamiltonian network, no efficient algorithm can guarantee a constant approximation better than 2. For general topologies, we offer a simple algorithm with an $\textit{O}(log$ $\textit{K})-$ and an $\textit{O}(log$ $\textit{n})-approximation,$ where $\textit{K}$ is the number of demands and $\textit{n}$ the number of nodes. This approximation ratio is almost tight. For rings, a common special topology, we offer a more complex 3/2-approximation algorithm.
Starting Page	1
Ending Page	20
Page Count	20
File Format	PDF
ISSN	15496325
e-ISSN	15496333
DOI	10.1145/1328911.1328926
Volume Number	4
Issue Number	1
Journal	ACM Transactions on Algorithms (TALG)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2008-03-28
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Optical network design Approximation algorithms Path decomposition
Content Type	Text
Resource Type	Article
Subject	Mathematics

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

Path decomposition under a new cost measure with applications to optical network design

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

Approximation algorithms for a facility location problem with service capacities

Path Decomposition of Graphs with Given Path Length

Approximation for a scheduling problem with application in wireless networks

Approximation via cost sharing: Simpler and better approximation algorithms for network design

Survivable Path Sets: A New Approach to Survivability in Multilayer Networks

Abstract IYER, PRASHANT. The Complexity of Traffic Grooming in Optical Path Networks with Egress

Decomposition by Successive Convex Approximation: A Unifying Approach for Linear Transceiver Design in Heterogeneous Networks

Path decomposition under a new cost measure with applications to optical network design

Similar Documents

Path decomposition under a new cost measure with applications to optical network design

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

Approximation algorithms for a facility location problem with service capacities

Path Decomposition of Graphs with Given Path Length

Approximation for a scheduling problem with application in wireless networks

Approximation via cost sharing: Simpler and better approximation algorithms for network design

Survivable Path Sets: A New Approach to Survivability in Multilayer Networks

Abstract IYER, PRASHANT. The Complexity of Traffic Grooming in Optical Path Networks with Egress

Decomposition by Successive Convex Approximation: A Unifying Approach for Linear Transceiver Design in Heterogeneous Networks

Path decomposition under a new cost measure with applications to optical network design