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 17 of 17 for “"MULTICOMMODITY FLOWS"”.
-
Uniform multicommodity flows in random networks
… vertices in 𝒩, a corresponding <em>uniform multicommodity flow</em> <em>F</em> of volume φ consists of simultaneous flows of volume φ of unique commodities between each pair of vertices in 𝒱. The <em>maximum uniform flow volume</em> is the maximum value of φ such that there is a uniform …
-
Branch-and-price and multicommodity flows
… and integer programming and apply them to three multicommodity flow problems. For (mixed) integer programming problems, the approach taken consists in reformulating an original model, using the Dantzig-Wolfe decomposition principle, and then combining column generation with branch-and-bound …
-
Topics in Combinatorial Algorithms (Multicommodity Flows, Quadratic Programming)
This thesis is a study of a wide variety of combinatorial optimization problems.
-
Directed multicommodity flows : cut-sufficiency and forbidden relevant minors
In a multicommodity flow problem, the goal is to route paths in a supply graph G to satisfy demands between vertices, represented by a demand graph H. This must be done simultaneously for all commodities, without exceeding edge capacities. To do this, there can be no cut where the requested demand …
-
Maximum Flows in Unit-Capacitated Multicommodity Trees
Multicommodity flows are studied, in the special case where the underlying graph is a tree and all arc capacities are one.
-
Dynamic multicommodity flow schedules
Some new results in the scheduling of dynamic multicommodity flows in data communication networks are presented. A new performance measure for effective delivery of backlogged data to their destinations is defined and the solution to the resulting delivery problem is obtained through a sequential …
-
On Robust Distributed Control of Transportation Networks
… control strategy can handle larger exogenous inflows to the network than the GPA-controller. Since the traffic signal controllers such as the GPA may allocate service to an empty line, due to the fact that several lanes can receive green light simultaneously, a model that handles this issue is …
-
Linear Programming Tools and Approximation Algorithms for Combinatorial Optimization
… We also investigate the areas of network design, multicommodity flows, and packing/covering integer programs. All of these problems are NP-complete so it is natural to seek approximation algorithms with the best provable approximation ratio. Overall, we show some new techniques that enhance the …
-
Approximation algorithms for submodular optimization and graph problems
… the gap between fractional and integral multicommodity flows. We give a poly-logarithmic approximation with constant congestion for the node-disjoint paths problem and we show a poly-logarithmic upper bound on the gap between the maximum fractional and integral throughput flows in …
-
Resource management in wireless networks and the smart power grid.
… yield (near-)optimal end-to-end rates, multicommodity flows, link capacities, and average powers. These design variables are obtained offline, and are subsequently used for control during network operation. Moreover, physical layer power allocation algorithms that are seamlessly …
-
Víceproduktové toky v sítích a jejich optimalizace
Diplomová práca sa zaoberá viacproduktovými tokmi v sieťach a ich optimalizáciou. V teoretickej časti sumarizuje základné pojmy tokov v sieťach, vzťah jednoproduktových a viacproduktových úloh, hlavné formulácie viacproduktového toku a vybrané metódy ich riešenia. Praktická časť je zameraná na …
-
ΕΥΡΕΤΙΚΗ ΠΡΟΣΕΓΓΙΣΗ ΣΤΟ ΠΡΟΒΛΗΜΑ ΤΟΥ ΣΧΕΔΙΑΣΜΟΥ ΔΙΚΤΥΟΥ ΜΕ ΠΑΓΙΑ ΚΑΙ ΜΕΤΑΒΛΗΤΑ ΣΤΟΙΧΕΙΑ ΚΟΣΤΟΥΣ
THE PURPOSE OF THIS THESIS IS THE STUDY OF THE MULTICOMMODITY NETWORK DESIGN PROBLEM WITH FIXED AND VARIABLE COST ELEMENTS (MNDP). WE EXAMINE THE ECONOMIC ASPECTS OF THE CAPACITY EXPANSION OF THE SYSTEMS WITH ECONOMIES OF SCALE, WHICH MAY APPROXIMATELY BE MODELLED AS MNDP. IT IS SUGGESTED IN WHAT …
-
Toky v sítích, algoritmy a aplikace
Tato diplomová práce popisuje algoritmy pro hledání maximálního toku v síti. Samotným algoritmům předchází seznámení se s problematikou toku v sítích, základními definicemi a pojmy. Je zde uvedena transformace problému na další grafové úlohy, využití maximálních toků v síti v praxi a víceproduktové …