Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 16 of 16 for “"Survivable network design"”.
-
Approximation Algorithms for Relative Survivable Network Design Problems
The Survivable Network Design (SND) problem is a classical and well-studied graph connectivity problem. Given a set of source-sink pairs and demands between them, SND asks one to compute a subgraph such that the number of paths between each pair meets their demand. SND is primarily interesting in …
-
Survivable network design with stepwise incremental cost function
… services, transferred in both public and private network, than ever before. The use of integration of computers with telecommunications has created a so-called “Information Age”. The advent of high capacity digital telecommunication facilities has made it possible for the huge amount of traffic to …
-
Node-weighted prize-collecting survivable network design problems
We consider node-weighted network design problems, in particular the survivable network design problem SNDP and its prize-collecting version PC-SNDP. The input consists of a node-weighted undirected graph $G=(V,E)$ and integral connectivity requirements $r(st)$ for each pair of nodes $st$. The goal …
-
Contributions towards survivable network design with uncertain traffic requirements
The objective in designing a communications network is to find the most cost efficient network design that specifies hardware devices to be installed, the type of transmission links to be installed, and the routing strategy to be followed. The volume of traffic that will be supported by the network …
-
Survivable network design problems with element and vertex connectivity requirements
… we consider degree-bounded element-connectivity Survivable Network Design Problem (Elem-SNDP) and degree-bounded Rooted k-outconnectivity Problem. We suggest bicriteria approximation algorithms that are motivated by Ene and Vakilian's work in [1] and Lau and Zhou's work in [2]. The algorithm …
-
Robust and Survivable Network Design Considering Uncertain Node and Link Failures
The network design is a planning process of placing system components to provide service or meet certain needs in an economical way. It has strong links to real application areas, such as transportation network, communication network, supply chain, power grid, water distribution systems, etc. In …
-
Fault-tolerance using shared path protection in wavelength division multiplexing optical transport networks
… division multiplexing (WDM) fiber optical networks in the future are intended to provide bandwidths in the range of 500-2000 Gbps with the number of wavelengths multiplexed onto a single fiber ranging from 100-200. The enormous bandwidth capacity of WDM networks have made …
-
Approximation Algorithms for Network Connectivity Problems
In this dissertation, we examine specific network connectivity problems, and achieve improved approximation algorithm and integrality gap results for them. We introduce an important new, highly useful and applicable, network connectivity problem - the Vital Core Connectivity Problem (VCC). Despite …
-
Iterative Rounding Approximation Algorithms in Network Design
… been an increasingly popular approach to solving network design optimization problems ever since Jain introduced the concept in his revolutionary 2-approximation for the Survivable Network Design Problem (SNDP). This paper looks at several important iterative rounding approximation algorithms and …
-
Online Network Design under Uncertainty
Today, computer and information networks play a significant role in the success of businesses, both large and small. Networks provide access to various services and resources to end users and devices. There has been extensive research on de- signing networks according to numerous criteria such as …
-
New tree-based algorithms for network spare capacity design
Survivable network design has become increasingly important due to the need for reliable communication service. One of its important components is the spare capacity design. Its main purpose is to provide cost-efficient spare capacity reservation at certain survivability level in case of predicted …
-
Optimization Methods for Optical Long-Haul and Access Networks
… fiber has been witnessed in backbone and metro networks as well as access segments connecting to customer premises and homes. Designing and developing a reliable, robust and efficient end-to-end optical communication system have thus emerged as topics of utmost importance both to researchers and …
-
Topics in Classical and Quantum Optimization: Complexity and Algorithms
… problem sizes. Extensions of the work to the survivable network design problem are discussed afterwards. We conclude the thesis with a general discussion on optimization, information and algorithmic complexity, and different computing technologies in relation to the content presented.
-
Algorithms and complexity analyses for some combinational optimization problems
… problems in two important areas: scheduling and network design. In the area of scheduling, the main interest is in problems in the master-slave model. In this model, each machine is either a master machine or a slave machine. Each job is associated with a preprocessing task, a slave task and a …
-
Valid Inequalities and Facets for Multi-Module (Survivable) Capacitated Network Design Problem
… and algorithms to solve the multi-module (survivable) network design problem. Many real-world decision-making problems can be modeled as network design problems, especially on networks with capacity requirements on arcs or edges. In most cases, network design problems of this type that have …
-
Approximation algorithms for submodular optimization and graph problems
… ratio possible. Our focus in this thesis is on designing approximation algorithms for several combinatorial optimization problems. In the first part of this thesis, we study a class of constrained submodular minimization problems. We introduce a model that captures allocation problems with …