Ingeniero Civil Matemático / La computación distribuida, rama de las ciencias de la computación, se focaliza en estu- diar sistemas distribuidos, tales como internet, redes sociales o protocolos de mensajería. La información se encuentra distribuida entre las distintas entidades que conforman el sistema y el objetivo último es resolver algún problema global. Para ello las distintas entidades se comunican mediante los canales de la red hasta que encuentran la solución. Esta memoria comienza estudiando el problema de la degenerancia de un grafo en los modelos de computación distribuida UCAST y BCAST, donde la degenerancia de un grafo G se define como el máximo grado mínimo de un subgrafo F de G. Los modelos distribuidos UCAST y BCAST corresponden a redes completas de n individuos, los cuales se comunican de manera síncrona por los canales de la red en rondas. En el primer caso, cada individuo por ronda puede enviar diferentes mensajes por cada uno de sus canales. En el segundo caso, cada individuo por ronda envía a través de sus canales el mismo mensaje. En general, se suele decir que BCAST es una restricción de UCAST. Primero, se construye un protocolo aleatorio en el modelo UCAST que calcula una (1 + ε)- aproximación de la degenerancia en O(log n) rondas con mensajes de largo O(log n). En el modelo BCAST se demuestra que el problema de calcular la degenerancia es difícil en 1 ronda. Más específicamente, se demuestra que todo protocolo aleatorio de 1 ronda que calcule exactamente la degenerancia debe enviar un mensaje de largo Ω(n). En el mismo modelo, se construye un protocolo aleatorio de 2 rondas con mensajes de largo O(log 2 n) que calcula una (1 + ε)-aproximación de la degenerancia para grafos α-densos. Finalmente, se construye un protocolo determinista que calcula una (2 + ε)-aproximación de la degenerancia en O(log n) rondas con mensajes de largo O(log n). Como segunda parte de este trabajo, y motivado por el protocolo en BCAST que calcula una (2 + ε)-aproximación de la degenerancia, se estudia la siguiente dinámica sobre grafos: Durante cada iteración, eliminar todos los vértices que tengan grado a lo más el grado prome- dio del grafo +1. Se conjetura que para todo grafo G de n vértices la dinámica toma O(log n) iteraciones en vaciar el grafo. Se aborda el problema estudiando clases de grafos tales como: bosques, grafos planares, grafos con degenerancia acotada y grafos unión disjunta de cliques. Finalmente, se estudian diversos problemas en el modelo BCAST. Se comienza estudiando el problema de calcular el conjunto independiente maximal con un vértice fijo. Se prueba que el problema es difícil en 1 ronda y luego se contruye un protocolo que en O(log n) rondas, usando mensaje de largo O(log n), calcula el conjunto independiente. Se estudia también el problema de calcular el número cromático de un grafo. Se prueba que el problema resulta difícil en 1 ronda. Concluyendo el capítulo, se estudian los problemas de encontrar conjuntos dominantes de tamaño k y conjuntos -dominantes de tamaño k, en ambos casos se demuestra que los problemas son difíciles en 1 ronda. / Este trabajo ha sido parcialmente financiado por Proyecto Fondecyt 1130061

In this report, we initiate study on understanding a theoretical model for distributed computing called Congested Clique. This report presents constant-time and near-constant-time distributed algorithms for a variety of problems in the Congested Clique model. We start by showing how to compute a 3-ruling set in expected O(log log log n) rounds and using this, we obtain a constant-approximation to metric facility location, also in expected O(log log log n) rounds. In addition, assuming an input metric space of constant doubling dimension, we obtain constant-round algorithms to compute maximal independent set on distance-threshold graphs and constant-factor approximation to the metric facility location problem. These results significantly improve on the running time of the fastest known algorithms for these problems in the Congested Clique setting. Then, we study two fundamental graph problems, Graph Connectivity (GC) and Minimum Spanning Tree (MST), in the Congested Clique model, and present several new bounds on the time and message complexities of randomized algorithms for these problems. No non-trivial (i.e., super-constant) time lower bounds are known for either of the aforementioned problems; in particular, an important open question is whether or not constant-round algorithms exist for these problems. We make progress toward answering this question by presenting randomized Monte Carlo algorithms for both problems that run in O(log log log n) rounds (where n is the size of the clique). In addition, assuming an input metric space of constant doubling dimension, we obtain constant-round algorithm the MST problem. Our results improve by an exponential factor on the long-standing (deterministic) time bound of O(log log n) rounds for these problems due to Lotker et al. (SICOMP 2005). Our algorithms make use of several algorithmic tools including graph sketching, random sampling, and fast sorting. Thus far there has been little work on understanding the message complexity of problems in the Congested Clique. In this report, we initiate a study on the message complexity of Congested Clique algorithms. We study two graph problems, Graph Connectivity (GC) and Minimum Spanning Tree (MST), in the Congested Clique model, focusing on the design of fast algorithms with low message complexity. Our motivation comes from recently established connections between the Congested Clique model and models of large-scale distributed computing such as MapReduce (Hegeman et al., SIROCCO 2014) and the “big data” model (Klauck et al., SODA 2015). For these connections to be fruitful, Congested Clique algorithms not only need to be fast, they also need to have low message complexity. While the aforementioned algorithms are fast, they have an Ω(n2) message complexity, which makes them impractical in the context of the MapReduce and “big data” models. This motivates our goal of achieving low message complexity, without sacrificing the speed of the algorithm. We start with the simpler GC problem and show that it can be solved in O(log log log n) rounds using only O(n poly log n) messages. Then we derive subroutines to aid our earlier MST algorithm to run in O(log log log n) rounds using O(m poly log n) messages on an m-edge input graph. Then, we present an algorithm running in O(log* n) rounds, with message complexity O (sqrt(m · n)) and then build on this algorithm to derive a family of algorithms, containing for any ε, 0 < ε ≤ 1, an algorithm running in O(log*n/ε) rounds, using O(n^(1+ε/ε)) messages. Setting ε = log log n/ log n leads to the first sub-logarithmic round Congested Clique MST algorithm that uses only O (n) messages. Our results are a step toward understanding the power of randomization in the Congested Clique with respect to both time and message complexity.

A planar single facility location problem, also known as the Fermat&ndash / Weber problem, is to

The purpose with this report is to develop a network based insertion algorithm and evaluate it on a real-case timetable. The aim of the algorithm is to minimize the effect that that train implementation cause on the other, already scheduled traffic. We meet this purpose by choosing an objective function that maximizes the minimum distance to a conflicting train path. This ensures that the inserted train receives the best possible bottleneck robustness. We construct a graph problem, which solve with a modified version of Dijkstra’s algorithm. The complexity of the algorithm is Ο(s^2 t log⁡(s^2 t). We applied the algorithm on a Swedish timetable, containing 76 stations. The algorithm performs well and manage to obtain the optimal solution for a range of scenarios, which we have evaluated in various experiments. Increased congestion seemed to reduce the problem size. The case also show that a solution’s robustness decreases with increasing total number of departures. One disadvantage with the algorithm is that it cannot detect the best solution among those using the same bottleneck. We propose a solution to this that we hope can be implemented in further studies.

No description available.

No description available.

No description available.

Over the last few decades there has been a gradual transformation in both the spatial and temporal patterns of urban activities. The percentage share of non-discretionary travel such as morning rush-hour commuting has been declining with the increased income level. Discretionary activities appear to rise prominently in urban business and leisure hubs, attracting large volumes of crowds which in turn imply new and changed demand for building floorspace and urban infrastructure. Despite impressive advances in the theories and models of infrastructure demand forecasting, there appear to be an apparent research gap in addressing the practical needs of infrastructure planning in and around those growing urban activity hubs. First, land use and transport interaction models which have to date been the mainstay of practical policy analytics tend to focus on non-discretionary activities such as rush-hour commuting. Secondly, the emerging activity based models, while providing significant new insights into personal, familial activities, especially the discretionary travel, are so data hungry and computing intensive that they have not yet found their roles in practical policy applications. This dissertation builds on the insights from above schools of modelling to develop a new approach that addresses the infrastructure planning needs of the growing urban hubs while keeping the data and computing realistic in medium to high income cities. The new model is designed based on an overarching hypothesis that considerable efficiency and welfare gains can be achieved in the planning and development of urban business and leisure hubs if the infrastructure provisions for discretionary and non-discretionary activities can be coordinated. This is a research theme that has been little explored in current literature. The new infrastructure demand forecasting model has been designed with regard to the above hypothesis and realistic data availability, including those emerging online. The model extends the framework of land use transport interaction models and aim to provide a practical modelling tool. Land use changes are accounted for when testing new infrastructure investment initiatives and especially the road and public transport loads are assessed throughout all time periods of a working day. The new contribution to the modelling methodology includes the extension to the land use transport interaction framework, the use of social media data for estimating night market activity distribution and a rapid estimation of road traffic speeds from Google directions API, and model validation. Another new contribution is the understanding of the nature and magnitude of future infrastructure demand through assessing three alternative land use scenarios: (1) business as usual, (2) inner city regeneration for a major business hub around the night market, and (3) dispersed suburban growth with distant subcentres. The model is able to assess the implications for future infrastructure demand and user welfare through discerning the distinct discretionary and non-discretionary activity patterns.

Utvecklingen av större städer förhindras för närvarande av kapacitetsbrist i elnätet. För dagens moderna samhälle är det inte rimligt att bygga nya fastigheter utan en garanti av tillgång till energi, både under byggnationen och det senare underhållet. Marknadsaktörer som belastar elnätet samtidigt är ett exempel på vad som leder till dessa överbelastade nät. Städernas totala energiförbrukning behöver inte nödvändigtvis justeras. Snarare måste förbrukningen under högbelastade tidpunkter flyttas till tidpunkter då belastningen är mindre, – näten måste alltså användas smartare. Detta innebär mycket ansvar för fastighetsägare som har stor inverkan på energiförbrukningen, eftersom dem har möjligheten att styra förbrukningen i sina fastigheter. Därför var syftet med projektet att låta fastighetsägarna på ett lätthanterlig och bekvämt sätt informera sina hyresgäster om förändringar som utförs i fastigheterna. Resultatet var implementation av ett tillägg till en mobilapplikation och i form av en molnbaserad databas, vilken kunde uppkopplas till fastighetens styrsystem. Vidare finns även möjlighet för fastighetsägare att ge hyresgäster förslag på vad de själva kan bidra med för att minska energianvändningen. Vår lösning kommer inte lösa hela kapacitetsbristen i elnäten, utan det är snarare en dellösning och ett steg närmre en smartare elanvändning och ett ändrat användarbeteende. En lösning som inte kräver utbyggnad av elnätet. / The development of larger cities is currently prevented by congested electricity grids. In today's modern society, it is not sensible to build new real estates without a guarantee of access to energy, both during the construction and the maintenance. Market participants who utilize the power grid simultaneously is an example of what leads to these congested grids. The cities' total energy consumption does not necessarily need be adjusted. Rather, the times of usage must be. This puts a great deal of responsibility on property owners who have a big impact on the energy consumption, because they have the power to control the consumption in their properties. Therefore, the purpose of the project was to allow the property owners in an easy-to-manage and convenient manner to inform their tenants of changes made inside the properties. The result was the implementation of an add on to a mobile application in the form of a cloud-based database, which could be connected to the database of the property's control system. Furthermore, through the application  property owners can give tenants suggestions on how they can contribute to reduce energy use. Our solution will not solve the entire capacity shortage in the  grids, but rather it is a partial solution and one step closer to a smarter electricity use and a changed user behaviour. A solution that does not require expansion of the power grid.

O objetivo da presente dissertação foi verificar o efeito da participação de jovens jogadores de futebol em competições com calendário congestionado (CC) nas medidas de desempenho físico, e comparar as acelerações (ACC), as desacelerações (DEC), a potência metabólica média (PM), distância total percorrida (DT) e distância percorrida em alta velocidade (DAV) em 24 jogadores de futebol juvenil (sub-15, n = 11 e sub-17, n = 13) expostos a campeonatos de CC e períodos regulares de calendário não congestionados (calendário regular; CR); como critério de retenção dos dados dos jogadores, adotou-se, a participação mínima de 75% do tempo total de jogo em cada partida. Adicionalmente as medidas de desempenho físico foram normalizadas pelo tempo de participação em minutos na partida. Foram analisados 10 jogos internacionais no formato de CC (5 para cada categoria), realizados durante 3 dias sucessivos, incluindo 2 dias com 2 jogos consecutivos jogados com intervalo de 4-5 horas; para estabelecer uma condição \"controle\", 10 jogos de CR, de cada categoria, foram analisados; os jogos de CR foram realizados com um intevalo de pelo menos 7 dias. Os jogadores usavam uma unidade GPS de 15 Hz com um acelerômetro triaxial de 100 Hz alocada em uma veste especial. Uma diferença classificada como digna de consideração (tamanho do efeito; TE> 0,20) entre CC e CR, foi observada para os parâmetros de desempenho físico ACC, DEC e PM, para sub-15 e sub-17, com valores mais elevados no CC. Enquanto que DT e DAV apresentaram valores superiores para CR, apenas para o sub-15. Contrariamente à hipótese levantada, os parâmetros de desempenho físico mostram que os jogadores juvenis de elite avaliados elevaram a intensidade do jogo quando participaram de torneio CC. Uma diminuição em ACC e DEC, do 1° tempo para o 2° tempo foi observada (sub-15 e sub-17) nos diferentes formatos de campeonato. No entanto, observou-se um aumento da PM do 1° tempo para o 2° tempo; com um aumento muito grande para ambas as categorias durante a CR; para o CC, a PM aumentou (1ª para a 2ª metade) para o sub-17, mas diminuiu para o sub-15. Os resultados do presente estudo, sugerem que os perfis de taxa de trabalho dos jogadores não são prejudicados no CC e que o desempenho físico aumentado nesse tipo de competição pode estar associado a uma estratégia de auto-regulação ou \"pacing\" da intensidade de realização das ações. Apesar das semelhanças para os dados de desempenho físico (sub-15 e sub-17), a PM para o sub-17 foi amplamente aumentada no CC (vs CR) em comparação com os valores de PM do sub-15; sugerindo assim, uma maior capacidade dos atletas, com um suposto nível mais elevado de treinamento (sub-17) em otimizar o desempenho físico neste tipo de competição. Estas informações podem servir como um meio alternativo e eficiente de representação do desempenho físico e auxiliar na organização de uma preparação específica de equipes participantes destes formatos de competições (CC); adicionalmente, os resultados indicam a importância de de considerar as medidas de ACC, DEC e PM na análise do desempenho físico de jovens jogadores, ao invés da utilização isolada de medidas relacionadas a DT e DAV / The aim of this study was to compare the physical performances in youth players during congested (CM) versus regular match (RM) schedules. The accelerations (ACC), decelerations (DEC), average metabolic power (MP), total distance covered (TD) and distance covered at high speed (HSD) were compared across congested match (CM; 10 international matches played over 3 successive days, including 2 days with 2 consecutive matches played with a 4-5 hr interval) and 10 regular non-congested match periods (RM), played with a 7-day interval between matches, in elite youth soccer players (U15, n=11; U17, n=13).; as criterion for retention of the players\' data, it was adopted, the minimum participation of 75% of the total match time of each game. In addition, all variables were normalized per min of on-field playing time. Each player wore a 15-Hz GPS unit coupled with a 100 Hz tri-axial accelerometer (SPI Elite, GPSports, Canberra, Australia A difference classified as worthy of consideration (effect size; ES > 0.20), between CM and RM, was observed for ACC, DEC and MP, for U15 and U17, with higher values in CM. While TD and HSD showed lower values for CM for u15. Contrary to the hypothesis, the relative values of the physical performance parameters were higher for CM. A decrease in ACC and DEC, from the 1st half to the 2nd half of the match was observed (U15 and U17) for both CM and RM. However, an increase in MP from the 1st half to the 2nd half of the match was observed; with a very large increase for both categories during the RM; during the CM, MP increased (1st half to the 2nd half) in the U7, but decreased in U15. The present findings suggest that the players work rate profiles are not impaired in CM and that the intensity of the match-play is increased in this type of competition, and might be associated to self-regulation or pacing strategy; despite the similarities for physical performance in U15 and U17), MP was largely increased in U17 during CM (vs CR) compared to U15; this result suggests that the higher the level of the conditioning, the greater the ability of the athlete in optimizing physical performance in this type of match schedule. This information can serve as an alternative and efficient means of representing physical performance and may help coaches to organize and monitor specific preparations of teams participating in these type of competitions (CM); additionally, the results indicate the importance of considering the ACC, DEC and MP measurements in the analysis of physical performance of young players, instead of using only measures related to total distance covered and distances covered at different speeds