Spelling suggestions: "subject:"[een] STABLE MATCHING"" "subject:"[enn] STABLE MATCHING""
1 |
Optimization and measurement in humanitarian operations: addressing practical needsSoldner, Mallory 27 August 2014 (has links)
This thesis focuses on three topics relevant to humanitarian applications: (i) stable and complete assignment of staff members to field offices, (ii) bottleneck management for transportation networks, and (iii) performance measurement of the food assistance supply chain.
The assignment and reassignment of personnel to jobs is a large-scale problem faced by many organizations including the military and multi-national organizations. Although successful algorithms have been developed that can ensure matchings that are stable (without incentive to deviate), not all practical concerns have been addressed by these algorithms. For example, the gap we study is that when staff members do not provide preference lists covering all jobs, a complete stable matching is not guaranteed. In the first part of the thesis, we model negotiations, which occur in practice, as part of the problem of matching all agents. We introduce algorithms and structural results for when the organization negotiates with specific agents to modify their preference lists and the centralized objective is to minimize the number or cost of negotiations required to achieve complete stable matchings.
An uncertain environment with disruptions is a reality faced by many humanitarian operations but not fully addressed in the literature. Transportation delays are often driven by reliability issues (e.g., customs delays, strikes, and the availability of transport), and the length of wait time can be influenced by congestion. In the second part of the thesis, we describe a queuing model with breakdowns to model delays in port and transportation corridors (the overland travel from discharge ports to delivery points). Using the model, we gain insights into where delays are most detrimental to system performance (i.e., the network's "bottleneck") in port and transportation corridors. We then include our delay modeling in a convex cost network flow model that determines optimal routing when several port and corridor options are available. Finally, we examine a resource allocation model for where to invest in improvements to minimize delay. Throughout, we compare solutions using the optimal approach to rules of thumb and identify important factors that might be missing in practical decision making currently.
Third, we present a case study on the implementation of supply chain key performance indicators (KPIs) at a large humanitarian organization. We describe (i) the phases necessary for a full implementation of supply chain KPIs at a humanitarian or non-profit organization, (ii) how to address strategy, mindset, and organizational barriers, and (iii) how to adapt commercial supply chain KPI frameworks to the humanitarian sector, factoring in implementation constraints present in the humanitarian sector that may impact KPI development.
Last, a conclusion chapter discusses areas where this research may or may not generalize for each of the three topics studied.
|
2 |
Scarf's Theorem and Applications in CombinatoricsRioux, Caroline January 2006 (has links)
A theorem due to Scarf in 1967 is examined in detail. Several versions of
this theorem exist, some which appear at first unrelated. Two versions
can be shown to be equivalent to a result due to Sperner in 1928: for
a proper labelling of the vertices in a simplicial subdivision of an n-simplex,
there exists at least one elementary simplex which carries all labels {0,1,..., n}.
A third version is more akin to Dantzig's simplex method and is also examined.
In recent years many new applications in combinatorics have been found,
and we present several of them. Two applications are in the area of fair division: cake cutting
and rent partitioning. Two others are graph theoretic: showing the existence
of a fractional stable matching in a hypergraph and the existence of a fractional kernel in a
directed graph. For these last two, we also show the second implies the first.
|
3 |
Complexité des dynamiques de jeux / Complexity of games dynamicsZeitoun, Xavier 13 June 2013 (has links)
La th´eorie de la complexit´e permet de classifier les probl`emes en fonction de leur difficult´e. Le cadre classique dans lequel elle s’applique est celui d’un algorithme centralis´e qui dispose de toutes les informations. Avec l’essor des r´eseaux et des architectures d´ecentralis´ees, l’algo- rithmique distribu´ee a ´et´e ´etudi´ee. Dans un grand nombre de probl`emes, en optimisation et en ´economie, les d´ecisions et les calculs sont effectu´es par des agents ind´ependants qui suivent des objectifs diff´erents dont la r´ealisation d´epend des d´ecisions des autres agents. La th´eorie des jeux est un cadre naturel pour analyser les solutions de tels probl`emes. Elle propose des concepts de stabilit´e, le plus classique ´etant l’´equilibre de Nash.Une mani`ere naturelle de calculer de telles solutions est de “ faire r´eagir “ les agents ; si un agent voit quelles sont les d´ecisions des autres joueurs ou plus g´en´eralement un “ ´etat du jeu “, il peut d´ecider de changer sa d´ecision pour atteindre son objectif faisant ainsi ´evoluer l’´etat du jeu. On dit que ces algorithmes sont des “ dynamiques “.On sait que certaines dynamiques convergent vers un concept de solution. On s’int´eresse `a la vitesse de convergence des dynamiques. Certains concepts de solutions sont mˆeme complets pour certaines classes de complexit´e ce qui rend peu vraisemblable l’existence de dynamiques simples qui convergent rapidement vers ces solutions. On a utilis´e alors trois approches pour obtenir une convergence rapide : am´eliorer la dynamique (en utilisant par exemple des bits al´eatoires), restreindre la structure du probl`eme, et rechercher une solution approch´ee.Sur les jeux de congestion, on a ´etendu les r´esultats de convergence rapide vers un ´equilibre de Nash approch´e aux jeux n´egatifs. Cependant, on a montr´e que sur les jeux sans contrainte de signe, calculer un ´equilibre de Nash approch´e est PLS-complet. Sur les jeux d ’appariement, on a ´etudi´e la vitesse de dynamiques concurrentes lorsque les joueurs ont une information partielle param´etr´ee par un r´eseau social. En particulier, on a am´elior´e des dynamiques naturelles afin qu’elles atteignent un ´equilibre enO(log(n)) tours (avec n le nombre de joueurs). / Complexity theory allows to classify problems by their algorithmic hardness. The classical framework in which it applies is the one of a centralized algorithm that knows every informa- tion. With the development of networks and decentralized architectures, distributed dynamics was studied. In many problems, in optimization or economy, actions and computations are made by independant agents that don’t share the same objective whose realization depends on the actions of other agents. Game theory is a natural framework to study solutions of this kind of problem. It provides solution concepts such as the Nash equilibrium.A natural way to compute these solutions is to make the agents “react” ; if an agent sees the actions of the other player, or more generally the state of the game, he can decide to change his decision to reach his objective and updates the state of the game. We call �dynamics� this kind of algorithms.We know some dynamics converges to a stable solution. We are interested by the speed of convergence of these dynamics. Some solution concepts are even complete for some complexity classes which make unrealistic the existence of fast converging dynamics. We used three ways to obtain a fast convergence : improving dynamics (using random bits), finding simple subcases, and finding an approximate solution.We extent fast convergence results to an approximate Nash equilibria in negative congestion games. However, we proved that finding an approximate Nash equilibrium in a congestion games without sign restriction is PLS-complete. On matching game, we studied the speed of concurrent dynamics when players have partial information that depends on a social network. Especially, we improved natural dynamics for them to reach an equilibrium inO(log(n)) rounds (with n is the number of players).
|
4 |
Scarf's Theorem and Applications in CombinatoricsRioux, Caroline January 2006 (has links)
A theorem due to Scarf in 1967 is examined in detail. Several versions of
this theorem exist, some which appear at first unrelated. Two versions
can be shown to be equivalent to a result due to Sperner in 1928: for
a proper labelling of the vertices in a simplicial subdivision of an n-simplex,
there exists at least one elementary simplex which carries all labels {0,1,..., n}.
A third version is more akin to Dantzig's simplex method and is also examined.
In recent years many new applications in combinatorics have been found,
and we present several of them. Two applications are in the area of fair division: cake cutting
and rent partitioning. Two others are graph theoretic: showing the existence
of a fractional stable matching in a hypergraph and the existence of a fractional kernel in a
directed graph. For these last two, we also show the second implies the first.
|
5 |
Radio Resource Management for Relay-Aided Device-to-Device CommunicationHasan, Monowar January 2014 (has links)
In this thesis, performance of relay-assisted Device-to-device (D2D) communication is investigated where D2D traffic is carried through relay nodes. I develop resource management schemes to maximize end-to-end rate as well as conversing rate requirements for cellular and D2D UEs under total power constraint. I also develop a low-complexity distributed solution using the concept of message passing. Considering the uncertainties in wireless links (e.g., when interference from other relay nodes and the link gains are not exactly known), I extend the formulation using robust resource allocation techniques. In addition, a distributed solution approach using stable matching is developed to allocate radio resources in an efficient and computationally inexpensive way under the bounded channel uncertainties. Numerical results show that, there is a distance threshold beyond which relay-assisted D2D communication significantly improves network performance at the cost of small increase in end-to-end delay when compared to conventional approach.
|
6 |
Efficient Workload and Resource Management in DatacentersXu, Hong 13 August 2013 (has links)
This dissertation focuses on developing algorithms and systems to improve the efficiency of operating mega datacenters with hundreds of thousands of servers. In particular, it seeks to address two challenges: First, how to distribute the workload among the set of datacenters geographically deployed across the wide area? Second, how to manage the server resources of datacenters using virtualization technology?
In the first part, we consider the workload management problem in geo-distributed datacenters. We first present a novel distributed workload management algorithm that jointly considers request mapping, which determines how to direct user requests to an appropriate datacenter for processing, and response routing, which decides how to select a path among the set of ISP links of a datacenter to route the response packets back to a user. In the next chapter, we study some key aspects of cost and workload in geo-distributed datacenters that have not been fully understood before. Through extensive empirical studies of climate data and cooling systems, we make a case for temperature aware workload management, where the geographical diversity of temperature and its impact on cooling energy efficiency can be used to reduce the overall cooling energy. Moreover, we advocate for holistic workload management for both interactive and batch jobs, where the delay-tolerant elastic nature of batch jobs can be exploited to further reduce the energy cost. A consistent 15% to 20% cooling energy reduction, and a 5% to 20% overall cost reduction are observed from extensive trace-driven simulations.
In the second part of the thesis, we consider the resource management problem in virtualized datacenters. We design Anchor, a scalable and flexible architecture that efficiently supports a variety of resource management policies. We implement a prototype of Anchor on a small-scale in-house datacenter with 20 servers. Experimental results and trace-driven simulations show that Anchor is effective in realizing various resource management policies, and its simple algorithms are practical to solve virtual machine allocation with thousands of VMs and servers in just ten seconds.
|
7 |
Efficient Workload and Resource Management in DatacentersXu, Hong 13 August 2013 (has links)
This dissertation focuses on developing algorithms and systems to improve the efficiency of operating mega datacenters with hundreds of thousands of servers. In particular, it seeks to address two challenges: First, how to distribute the workload among the set of datacenters geographically deployed across the wide area? Second, how to manage the server resources of datacenters using virtualization technology?
In the first part, we consider the workload management problem in geo-distributed datacenters. We first present a novel distributed workload management algorithm that jointly considers request mapping, which determines how to direct user requests to an appropriate datacenter for processing, and response routing, which decides how to select a path among the set of ISP links of a datacenter to route the response packets back to a user. In the next chapter, we study some key aspects of cost and workload in geo-distributed datacenters that have not been fully understood before. Through extensive empirical studies of climate data and cooling systems, we make a case for temperature aware workload management, where the geographical diversity of temperature and its impact on cooling energy efficiency can be used to reduce the overall cooling energy. Moreover, we advocate for holistic workload management for both interactive and batch jobs, where the delay-tolerant elastic nature of batch jobs can be exploited to further reduce the energy cost. A consistent 15% to 20% cooling energy reduction, and a 5% to 20% overall cost reduction are observed from extensive trace-driven simulations.
In the second part of the thesis, we consider the resource management problem in virtualized datacenters. We design Anchor, a scalable and flexible architecture that efficiently supports a variety of resource management policies. We implement a prototype of Anchor on a small-scale in-house datacenter with 20 servers. Experimental results and trace-driven simulations show that Anchor is effective in realizing various resource management policies, and its simple algorithms are practical to solve virtual machine allocation with thousands of VMs and servers in just ten seconds.
|
8 |
Modelos matemáticos e algoritmos para problemas combinatóriosRavelo, Santiago Valdes 18 February 2011 (has links)
Submitted by Erika Demachki (erikademachki@gmail.com) on 2016-03-17T17:31:58Z
No. of bitstreams: 2
Dissertação - Santiago Valdés Ravelo - 2011.pdf: 730949 bytes, checksum: 92c89c8c1f240082004834898896b9ba (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Erika Demachki (erikademachki@gmail.com) on 2016-03-17T17:35:15Z (GMT) No. of bitstreams: 2
Dissertação - Santiago Valdés Ravelo - 2011.pdf: 730949 bytes, checksum: 92c89c8c1f240082004834898896b9ba (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2016-03-17T17:35:15Z (GMT). No. of bitstreams: 2
Dissertação - Santiago Valdés Ravelo - 2011.pdf: 730949 bytes, checksum: 92c89c8c1f240082004834898896b9ba (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)
Previous issue date: 2011-02-18 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work considers three relevant NP-hard problems. The firstone is the one-dimensional
cutting stock problem in which the non-used material in the cutting patterns may be used
in the future. For this problem we analyze the existing mathematical models, propose new
models, design a heuristic and two metaheuristic approaches, being their performances
improved by using parallel programming, and solve instances, practical and randomly
generated, from the literature. The computational experiments were quite good for all
tested instances. The second problem we consider is the stable roommates problem (a
variant of the stable matching problem). For this we give two mathematical programming
models, sequential and parallel implementations of a Tabu Search, and a Branch-andBound. Also, we report computational experiments to instances of the problem. The
last problem we consider is the compartmentalized knapsack problem (a generalization
of the knapsack problem) for which we analyze a quadratic integer model and give a
linear integer model. We design a greedy heuristic and a GRASP algorithm, that uses
path-relinking, and solve randomly generated instances. All parallel implementations use
Graphics Processing Units (GPUs). / Este trabalho considera três problemas, NP-difíceis, relevantes de estudo em otimização
combinatória. O primeiro deles é o problema de corte uni-dimensional de objetos,
onde o material não usado pelos padrões de corte pode ser usado no futuro. Para este
problema analisamos os modelos matemáticos existentes, propomos novos modelos,
projetamos uma heurística construtiva e duas metaheurísticas, sendo seus desempenhos
melhorados com programação paralela, e resolvemos instâncias, práticas e aleatórias,
encontradas na literatura; sendo os experimentos computacionais muito bons para todas as
intânciastestadas.Osegundoproblemaqueconsideramoséoproblemadoscompanheiros
estáveis (stable roommates problem), uma variante do problema de emparelhamento
estável (stable matching problem). Para este propomos dois modelos matemáticos, uma
implementação sequencial e uma paralela de uma Tabu Search, e um Branch-andBound. Também reportamos experimentos computacionais para instâncias do problema.
O último problema considerado é o da mochila compartimentada (uma generalização do
problema clássico da mochila), para o qual analisamos uma modelagem quadrática inteira
e propomos um modelo linear inteiro; também projetamos uma heurística gulosa, um
algoritmo GRASP, que usa path-relinking, e resolvemos intâncias geradas aleatóriamente.
Todas as implementações em paralelo usam unidades de processamento gráfico (Graphics
Processing Units, GPUs).
|
9 |
Analysis and optimisation of stable matching in combined input and output queued switchesSchweizer, Andreas January 2009 (has links)
Output queues in network switches are known to provide a suitable architecture for scheduling disciplines that need to provide quality of service (QoS) guarantees. However, todays memory technology is incapable of meeting the speed requirements. Combined input and output queued (CIOQ) switches have emerged as one alternative to address the problem of memory speed. When a switch of this architecture uses a stable matching algorithm to transfer packets across the switch fabric, an output queued (OQ) switch can be mimicked exactly with a speedup of only two. The use of a stable matching algorithm typically requires complex and time-consuming calculations to ensure the behaviour of an OQ switch is maintained. Stable matching algorithms are well studied in the area in which they originally appeared. However, little is presently known on how the stable matching algorithm performs in CIOQ switches and how key parameters are affected by switch size, traffic type and traffic load. Knowledge of how these conditions affect performance is essential to judge the practicability of an architecture and to provide useful information on how to design such switches. Until now, CIOQ switches were likely to be dismissed due to the high complexity of the stable matching algorithm when applied to other applications. However, the characteristics of a stable matching algorithm in a CIOQ switch have not been thoroughly analysed. The principal goal of this thesis is to identify the conditions the stable matching algorithm encounters in a CIOQ switch under realistic operational scenarios. This thesis provides accurate mathematical models based on Markov chains to predict the value of key parameters that affect the complexity and runtime of a stable matching algorithm in CIOQ switches. The applicability of the models is then backed up by simulations. The results of the analysis quantify critical operational parameters, such as the size and number of preference lists and runtime complexity. These provide detailed insights into switch behaviour and useful information for switch designs. Major conclusions to be drawn from this analysis include that the average values of the key parameters of the stable matching algorithm are feasibly small and do not strongly correlate with switch size, which is contrary to the behaviour of the stable matching ii algorithm in its original application. Furthermore, although these parameters have wide theoretical ranges, the mean values and standard deviations are found to be small under operational conditions. The results also suggest that the implementation becomes very versatile as the completion time of the stable matching algorithm is not strongly correlated to the network traffic type; that is, the runtime is minimally affected by the nature of the traffic.
|
10 |
Algorithms for Stable Matching Problems toward Real-World Applications / 現実世界での応用に向けた安定マッチング問題のアルゴリズムHamada, Koki 23 March 2022 (has links)
京都大学 / 新制・課程博士 / 博士(情報学) / 甲第24030号 / 情博第786号 / 新制||情||133(附属図書館) / 京都大学大学院情報学研究科知能情報学専攻 / (主査)准教授 宮崎 修一, 教授 岡部 寿男, 教授 阿久津 達也, 教授 湊 真一 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM
|
Page generated in 0.0389 seconds