Traditionally, optimization problems in operations research have been studied in a complete information setting; the input/data is collected and made fully accessible to the user, before an algorithm is sequentially run to generate the optimal output. However, the growing magnitude of treated data and the need to make immediate decisions are increasingly shifting the focus to optimizing under incomplete information settings. The input can be partially inaccessible to the user either because it is generated continuously, contains some uncertainty, is too large and cannot be stored on a single machine, or has a hidden structure that is costly to unveil. Many problems providing a context for studying algorithms when the input is not entirely accessible emanate from the field of matching theory, where the objective is to pair clients and servers or, more generally, to group clients in disjoint sets. Examples include ride-sharing and food delivery platforms, internet advertising, combinatorial auctions, and online gaming. In this thesis, we study three different novel problems from the theory of matchings. These problems correspond to situations where the input is hidden, spread across multiple processors, or revealed in two stages with some uncertainty. In particular, we present in Chapter 1 the necessary definitions and terminology for the concepts and problems we cover. In Chapter 2, we consider a two-stage robust optimization framework that captures matching problems where one side of the input includes some future demand uncertainty. We propose two models to capture the demand uncertainty: explicit and implicit scenarios. Chapters 3 and 4 see us switch our attention to matchings in hypergraphs. In Chapter 3, we consider the problem of learning hidden hypergraph matchings through membership queries. Finally, in Chapter 4, we study the problem of finding matchings in uniform hypergraphs in the massively parallel computation (MPC) model where the data (e.g. vertices and edges) is distributed across the machines and in each round, a machine performs local computation on its fragment of data, and then sends messages to other machines for the next round.

Emerging wireless networks are foreseen as an integration of heterogeneous spectrum bands, wireless access technologies, and backhaul solutions, as well as a large-scale interconnection of devices, people, and vehicles. Such a heterogeneity will range from the proliferation of multi-tasking user devices with different capabilities such as smartphones and tablets to the deployment of multi-mode access points that can operate over heterogeneous frequency bands spanning both sub-6 GHz microwave and high-frequency millimeter wave (mmW) frequencies bands. This heterogeneous ecosystem will yield new challenges and opportunities for wireless resource management. On the one hand, resource management can exploit user and network-specific context information, such as application type, social metrics, or operator pricing, to develop application-driven, context-aware networks. Similarly, multiple frequency bands can be leveraged to meet the stringent and heterogeneous quality-of-service (QoS) requirements of the new wireless services such as video streaming and interactive gaming. On the other hand, resource management in such heterogeneous, multi-band, and large-scale wireless systems requires distributed frameworks that can effectively utilize all available resources while operating with manageable overhead. The key goal of this dissertation is therefore to develop novel, self-organizing, and low-complexity resource management protocols -- using techniques from matching theory, optimization, and machine learning -- to address critical resource allocation problems for emerging heterogeneous wireless systems while explicitly modeling and factoring diverse network context information. Towards achieving this goal, this dissertation makes a number of key contributions. First, a novel context-aware scheduling framework is developed for enabling dual-mode base stations to efficiently and jointly utilize mmW and microwave frequency resources while maximizing the number of user applications whose stringent delay requirements are satisfied. The results show that the proposed approach will be able to significantly improve the QoS per application and decrease the outage probability. Second, novel solutions are proposed to address both network formation and resource allocation problems in multi-hop wireless backhaul networks that operate at mmW frequencies. The proposed framework motivates collaboration among multiple network operators by resource sharing to reduce the cost of backhauling, while jointly accounting for both wireless channel characteristics and economic factors. Third, a novel framework is proposed to exploit high-capacity mmW communications and device-level caching to minimize handover failures as well as energy consumption by inter-frequency measurements, and to provide seamless mobility in dense heterogeneous mmW-microwave small cell networks (SCNs). Fourth, a new cell association algorithm is proposed, based on matching theory with minimum quota constraints, to optimize load balancing in integrated mmW-microwave networks. Fifth, a novel medium access control (MAC) protocol is proposed to dynamically manage the wireless local area network (WLAN) traffic jointly over the unlicensed 60 GHz mmW and sub-6 GHz bands to maximize the saturation throughput and minimize the delay experienced by users. Finally, a novel resource management approach is proposed to optimize device-to-device (D2D) communications and improve traffic offload in heterogeneous wireless SCNs by leveraging social context information that is dynamically learned by the network. In a nutshell, by providing novel, context-aware, and self-organizing frameworks, this dissertation addresses fundamentally challenging resource management problems that mainly stem from large scale, stringent service requirements, and heterogeneity of next-generation wireless networks. / Ph. D. / The emergence of bandwidth-intensive applications along with vast proliferation of smart, multi-tasking handhelds have strained the capacity of wireless networks. Furthermore, the landscape of wireless communications is shifting towards providing connectivity, not only to humans, but also to automated cars, drones, and robots, among other critical applications. These new technologies will enable devices, machines, and things to be more intuitive, while being more capable, in order to improve the quality of life for human. For example, in future networked life, smartphones will predict our needs and help us with providing timely and relevant information from our surrounding. As an another example, autonomous vehicles and smart transportation systems with large number of connected safety features will minimize road incidents and yield a safe and joyful driving experience. Turning such emerging services into reality will require new technology innovations that provide high efficiency and substantial levels of scalability. To this end, wireless communication is the key candidate to provide large-scale and ubiquitous connectivity. However, existing wireless networks operate at congested microwave (µW) frequency bands and cannot manage the exponential growth in wireless data traffic or support low latency and ultra-high reliability communications, required by many emerging critical applications. Therefore, the goal of this dissertation is to develop novel network resource utilization frameworks to efficiently manage the heterogeneous traffic in next-generation wireless networks, while meeting their stringent quality-of-service (QoS) requirements. This transformative, fundamental research will expedite the deployment of communications at very high frequencies, at the millimeter wave (mmW) frequency bands, in next-generation wireless networks. The developed frameworks will advance new concepts from matching theory and machine learning for resource management in cellular networks, wireless local area networks (WLANs), and the intersection of these systems at both mmW and µW unlicensed frequency bands. This multi-band networking will leverage the synergies between mmW and µW wireless networks to provide robust and cost-effective solutions that enable the support of heterogeneous traffic from future wireless services. The anticipated results will transform the way in which spectral and time resources are used in both cellular networks and WLANs.

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, today’s 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.

Abstract Future cellular networks need to support the ever-increasing demand of bandwidth-intensive applications and interconnection of people, devices, and vehicles. Small cell network (SCN)-based communication together with proximity- and social-aware connectivity is conceived as a vital component of these networks to enhancing spectral efficiency, system capacity, and quality-of-experience (QoE). To cope with diverse application needs for the heterogeneous ecosystem, radio resource management (RRM) is one of the key research areas for the fifth-generation (5G) network. The key goals of this thesis are to develop novel, self-organizing, and low-complexity resource management algorithms for emerging device-to-device (D2D) and vehicle-to-vehicle (V2V) wireless systems while explicitly modeling and factoring network contextual information to satisfy the increasingly stringent requirements. Towards achieving this goal, this dissertation makes a number of key contributions. First, the thesis focuses on interference management techniques for D2D-enabled macro network and D2D-enabled SCNs in the downlink, while leveraging users’ social-ties, dynamic clustering, and user association mechanisms for network capacity maximization. A flexible social-aware user association technique is proposed to maximize network capacity. The second contribution focuses on ultra-reliable low-latency communication (URLLC) in vehicular networks in which interference management and resource allocation techniques are investigated, taking into account traffic and network dynamics. A joint power control and resource allocation mechanism is proposed to minimize the total transmission power while satisfying URLLC constraints. To overcome these challenges, novel algorithms are developed by combining several methodologies from graph theory, matching theory and Lyapunov optimization. Extensive simulations validate the performance of the proposed approaches, outperforming state-of-the-art solutions. Notably, the results yield significant performance gains in terms of capacity, delay reductions, and improved reliability as compared with conventional approaches. / Tiivistelmä Tulevaisuuden solukkoverkkojen pitää pystyä tukemaan yhä suurempaa kaistanleveyttä vaativia sovelluksia sekä yhteyksiä ihmisten, laitteiden ja ajoneuvojen välillä. Piensoluverkkoihin (SCN) pohjautuvaa tietoliikennettä yhdistettynä paikka- ja sosiaalisen tietoisuuden huomioiviin verkkoratkaisuihin pidetään yhtenä elintärkeänä osana tulevaisuuden solukkoverkkoja, joilla pyritään tehostamaan spektrinkäytön tehokkuutta, järjestelmän kapasiteettia sekä kokemuksen laatua (QoE). Radioresurssien hallinta (RRM) on eräs keskeisistä viidennen sukupolven (5G) verkkoihin liittyvistä tutkimusalueista, joilla pyritään hallitsemaan heterogeenisen ekosysteemin vaihtelevia sovellustarpeita. Tämän väitöstyön keskeisinä tavoitteina on kehittää uudenlaisia itseorganisoituvia ja vähäisen kompleksisuuden resurssienhallinta-algoritmeja laitteesta-laitteeseen (D2D) ja ajoneuvosta-ajoneuvoon (V2V) toimiville uusille langattomille järjestelmille, sekä samalla mallintaa ja tuottaa verkon kontekstikohtaista tietoa vastaamaan koko ajan tiukentuviin vaatimuksiin. Tämä väitöskirja edistää näiden tavoitteiden saavuttamista usealla keskeisellä tuloksella. Aluksi väitöstyössä keskitytään häiriönhallinnan tekniikoihin D2D:tä tukevissa makroverkoissa ja laskevan siirtotien piensoluverkoissa. Käyttäjän sosiaalisia yhteyksiä, dynaamisia ryhmiä sekä osallistamismekanismeja hyödynnetään verkon kapasiteetin maksimointiin. Verkon kapasiteettia voidaan kasvattaa käyttämällä joustavaa sosiaaliseen tietoisuuteen perustuvaa osallistamista. Toinen merkittävä tulos keskittyy huippuluotettavaan lyhyen viiveen kommunikaatioon (URLLC) ajoneuvojen verkoissa, joissa tehtävää resurssien allokointia ja häiriönhallintaa tutkitaan liikenteen ja verkon dynamiikka huomioiden. Yhteistä tehonsäädön ja resurssien allokoinnin mekanismia ehdotetaan kokonaislähetystehon minimoimiseksi samalla, kun URLLC rajoitteita noudatetaan. Jotta esitettyihin haasteisiin voidaan vastata, väitöstyössä on kehitetty uudenlaisia algoritmeja yhdistämällä graafi- ja sovitusteorioiden sekä Lyapunovin optimoinnin menetelmiä. Laajat tietokonesimuloinnit vahvistavat ehdotettujen lähestymistapojen suorituskyvyn, joka on parempi kuin uusimmilla nykyisillä ratkaisuilla. Tulokset tuovat merkittäviä suorituskyvyn parannuksia erityisesti kapasiteetin lisäämisen, viiveiden vähentämisen ja parantuneen luotettavuuden suhteen verrattuna perinteisiin lähestymistapoihin.

L’objectif de cette thèse est d’étudier l’impact de la fatigue du consommateur sur son traitement de l’information ublicitaire. Plus précisément, nous désirons comprendre comment la fatigue influence le processus de traitement visuel de la publicité, ainsi que les attitudes et la mémorisation. En nous appuyant sur la théorie d’adéquation des ressources, nous postulons que le traitement de l’information publicitaire, et donc l’efficacité de la publicité, est optimal quand le niveau de ressources cognitives disponible (niveau de fatigue du consommateur) correspond au niveau de ressources exigé (niveau de complexité de la publicité). Nos résultats mettent en lumière des effets de la fatigue différents selon les deux échantillons de notre recherche (étudiants et salariés). Les étudiants fatigués adoptent une stratégie visuelle de balayage pour compenser les effets de la fatigue et rendre le traitement de l’information plus facile. Les salariés fatigués adoptent une stratégie visuelle d’attention soutenue consistant à mobiliser le peu de ressources disponibles pour traiter l’information de façon efficace. Cette stratégie visuelle d’attention soutenue a un impact positif sur la mémorisation de la publicité. Nous montrons enfin que la théorie d’adéquation des ressources n’est pas le cadre théorique approprié pour étudier notre objet de recherche. En effet, les ressources cognitives s’avèrent être dynamiques : si elles y sont motivées, les personnes peuvent adapter leur niveaude ressources à la tache à accomplir. Les implications théoriques, méthodologiques et managériales de ces résultats sont discutées. / This research aims at studying the impact of consumers’ tiredness on the way they perceive and process advertising information. More specifically, we try to understand how tiredness influences advertisements’ visual processing as well as consumers’ attitudes and memorization. Relying on Resource Matching theory, we hypothesize that advertising informationprocessing, and therefore advertising efficiency, is optimal when the level of available resources (consumers’ tiredness) matches the level of required resources (advertisement complexity). Results show that the impact of tiredness differs according to sample under consideration (students or staff members). Tired students adopt a “screening” visual strategyin order to compensate for tiredness effects and ease their information processing. Tired staff members adopt a “sustained attention” visual strategy consisting in mobilizing their few available resources in order to efficiently process information. In this second case, sustained visual attention leads to better advertising memorization. We show that the Resource Matching theory is not the appropriate theoretical framework to study our research object. Indeed, we find that cognitive resources are dynamic:if motivated to do so, individuals are able to adapt their resource level according to the processing task. Theoretical, methodological and managerial implications are discussed.

Approximate pattern matching problem is, given a reference sequence T, a pattern (query) Q, and a maximum allowed error e, to find all the substrings in the reference, such that the edit distance between the substrings and the pattern is smaller than or equal to the maximum allowed error. Though it is a well-studied problem in Computer Science, it gains a resurrection in Bioinformatics in recent years, largely due to the emergence of the next-generation high-throughput sequencing technologies. This thesis contributes in a novel generalized pattern matching framework, and applies it to solve pattern matching problems in general and alternative splicing detection (AS) in particular. AS is to map a large amount of next-generation sequencing short reads data to a reference human genome, which is the first and an important step in analyzing the sequenced data for further Biological analysis. The four parts of my research are as follows. / In the first part of my research work, we propose a novel deterministic pattern matching algorithm which applies Agrep, a well-known bit-parallel matching algorithm, to a truncated suffix array. Due to the linear cost of Agrep, the cost of our approach is linear to the number of characters processed in the truncated suffix array. We analyze the matching cost theoretically, and .obtain empirical costs from experiments. We carry out experiments using both synthetic and real DNA sequence data (queries) and search them in Chromosome-X of a reference human genome. The experimental results show that our approach achieves a speed-up of several magnitudes over standard Agrep algorithm. / In the fourth part, we focus on the seeding strategies for alternative splicing detection. We review the history of seeding-and-extending (SAE), and assess both theoretically and empirically the seeding strategies adopted in existing splicing detection tools, including Bowtie's heuristic and ABMapper's exact seedings, against the novel complementary quad-seeding strategy we proposed and the corresponding novel splice detection tool called CS4splice, which can handle inexact seeding (with errors) and all 3 types of errors including mismatch (substitution), insertion, and deletion. We carry out experiments using short reads (queries) of length 105bp comprised of several data sets consisting of various levels of errors, and align them back to a reference human genome (hg18). On average, CS4splice can align 88. 44% (recall rate) of 427,786 short reads perfectly back to the reference; while the other existing tools achieve much smaller recall rates: SpliceMap 48.72%, MapSplice 58.41%, and ABMapper 51.39%. The accuracies of CS4splice are also the highest or very close to the highest in all the experiments carried out. But due to the complementary quad-seeding that CS4splice use, it takes more computational resources, about twice (or more) of the other alternative splicing detection tools, which we think is practicable and worthy. / In the second part, we define a novel generalized pattern (query) and a framework of generalized pattern matching, for which we propose a heuristic matching algorithm. Simply speaking, a generalized pattern is Q 1G1Q2 ... Qc--1Gc--1 Qc, which consists of several substrings Q i and gaps Gi occurring in-between two substrings. The prototypes of the generalized pattern come from several real Biological problems that can all be modeled as generalized pattern matching problems. Based on a well-known seeding-and-extending heuristic, we propose a dual-seeding strategy, with which we solve the matching problem effectively and efficiently. We also develop a specialized matching tool called Gpattern-match. We carry out experiments using 10,000 generalized patterns and search them in a reference human genome (hg18). Over 98.74% of them can be recovered from the reference. It takes 1--2 seconds on average to recover a pattern, and memory peak goes to a little bit more than 1G. / In the third part, a natural extension of the second part, we model a real biological problem, alternative splicing detection, into a generalized pattern matching problem, and solve it using a proposed bi-directional seeding-and-extending algorithm. Different from all the other tools which depend on third-party tools, our mapping tool, ABMapper, is not only stand-alone but performs unbiased alignments. We carry out experiments using 427,786 real next-generation sequencing short reads data (queries) and align them back to a reference human genome (hg18). ABMapper achieves 98.92% accuracy and 98.17% recall rate, and is much better than the other state-of-the-art tools: SpliceMap achieves 94.28% accuracy and 78.13% recall rate;while TopHat 88.99% accuracy and 76.33% recall rate. When the seed length is set to 12 in ABMapper, the whole searching and alignment process takes about 20 minutes, and memory peak goes to a little bit more than 2G. / Ni, Bing. / Adviser: Kwong-Sak Leung. / Source: Dissertation Abstracts International, Volume: 73-06, Section: B, page: . / Thesis (Ph.D.)--Chinese University of Hong Kong, 2011. / Includes bibliographical referencesTexture mapping (leaves 151-161). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [201-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. Ann Arbor, MI : ProQuest Information and Learning Company, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese.

by Chi-Min Pang. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1996. / Includes bibliographical references (leaves 110-[115]). / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Range Images --- p.1 / Chapter 1.2 --- Rigid Body Model --- p.3 / Chapter 1.3 --- Motivation --- p.4 / Chapter 1.4 --- Thesis Outline --- p.6 / Chapter 2 --- Object Recognition by Relaxation Processes --- p.7 / Chapter 2.1 --- An Overview of Probabilistic Relaxation Labelling --- p.8 / Chapter 2.2 --- Formulation of Model-matching Problem Solvable by Probabilistic Relaxation --- p.10 / Chapter 2.2.1 --- Compatibility Coefficient --- p.11 / Chapter 2.2.2 --- Match Score --- p.13 / Chapter 2.2.3 --- Iterative Algorithm --- p.14 / Chapter 2.2.4 --- A Probabilistic Concurrent Matching Scheme --- p.15 / Chapter 2.3 --- Formulation of Model-merging Problem Solvable by Fuzzy Relaxation --- p.17 / Chapter 2.3.1 --- Updating Mechanism --- p.17 / Chapter 2.3.2 --- Iterative Algorithm --- p.19 / Chapter 2.3.3 --- Merging Sub-Rigid Body Models --- p.20 / Chapter 2.4 --- Simulation Results --- p.21 / Chapter 2.4.1 --- Experiments in Model-matching Using Probabilistic Relaxation --- p.22 / Chapter 2.4.2 --- Experiments in Model-matching Using Probabilistic Concur- rent Matching Scheme --- p.26 / Chapter 2.4.3 --- Experiments in Model-merging Using Fuzzy Relaxation --- p.33 / Chapter 2.5 --- Summary --- p.36 / Chapter 3 --- Object Recognition by Hopfield Network --- p.37 / Chapter 3.1 --- An Overview of Hopfield Network --- p.38 / Chapter 3.2 --- Model-matching Problem Solved by Hopfield Network --- p.41 / Chapter 3.2.1 --- Representation of the Solution --- p.41 / Chapter 3.2.2 --- Energy Function --- p.42 / Chapter 3.2.3 --- Equations of Motion --- p.46 / Chapter 3.2.4 --- Interpretation of Solution --- p.49 / Chapter 3.2.5 --- Convergence of the Hopfield Network --- p.50 / Chapter 3.2.6 --- Iterative Algorithm --- p.51 / Chapter 3.3 --- Estimation of Distance Threshold Value --- p.53 / Chapter 3.4 --- Cooperative Concurrent Matching Scheme --- p.55 / Chapter 3.4.1 --- Scheme for Recognizing a Single Object --- p.56 / Chapter 3.4.2 --- Scheme for Recognizing Multiple Objects --- p.60 / Chapter 3.5 --- Simulation Results --- p.60 / Chapter 3.5.1 --- Experiments in the Model-matching Problem Using a Hopfield Network --- p.61 / Chapter 3.5.2 --- Experiments in Model-matching Problem Using Cooperative Concurrent Matching --- p.69 / Chapter 3.5.3 --- Experiments in Model-merging Problem Using Hopfield Network --- p.77 / Chapter 3.6 --- Summary --- p.80 / Chapter 4 --- Genetic Generation of Weighting Parameters for Hopfield Network --- p.83 / Chapter 4.1 --- An Overview of Genetic Algorithms --- p.84 / Chapter 4.2 --- Determination of Weighting Parameters for Hopfield Network --- p.86 / Chapter 4.2.1 --- Chromosomal Representation --- p.87 / Chapter 4.2.2 --- Initial Population --- p.88 / Chapter 4.2.3 --- Evaluation Function --- p.88 / Chapter 4.2.4 --- Genetic Operators --- p.89 / Chapter 4.2.5 --- Control Parameters --- p.91 / Chapter 4.2.6 --- Iterative Algorithm --- p.94 / Chapter 4.3 --- Simulation Results --- p.95 / Chapter 4.3.1 --- Experiments in Model-matching Problem using Hopfield Net- work with Genetic Generated Parameters --- p.95 / Chapter 4.3.2 --- Experiments in Model-merging Problem Using Hopfield Network --- p.101 / Chapter 4.4 --- Summary --- p.104 / Chapter 5 --- Conclusions --- p.106 / Chapter 5.1 --- Conclusions --- p.106 / Chapter 5.2 --- Suggestions for Future Research --- p.109 / Bibliography --- p.110 / Chapter A --- Proof of Convergence of Fuzzy Relaxation Process --- p.116

Mémoire (M. Sc. A.) --Université du Québec à Chicoutimi, 1988. / Bibliogr. : f. 104-105. Document électronique également accessible en format PDF. CaQCU

Orientador: Christiane Neme Campos / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-24T00:02:03Z (GMT). No. of bitstreams: 1 Galvao_KaioKaram_M.pdf: 1971760 bytes, checksum: e2f60ab09595b03fa6da5051cd78e3f3 (MD5) Previous issue date: 2013 / Resumo: Em 1971, Fulkerson propôs a seguinte conjetura: todo grafo cúbico sem arestas de corte admite seis emparelhamentos perfeitos tais que cada aresta do grafo pertence a exatamente dois destes emparelhamentos. A Conjetura de Fulkerson tem desafiado pesquisadores desde sua publicação. Esta conjetura é facilmente verificada para grafos cúbicos 3-aresta-coloráveis. Portanto, a dificuldade do problema reside em estabelecer a conjetura para grafos cúbicos sem arestas de corte que não possuem 3-coloração de arestas. Estes grafos são chamados snarks. Nesta dissertação, a Conjetura de Fulkerson e os snarks são introduzidos com ¿ênfase em sua história e resultados mais relevantes. Alguns resultados relacionados à Conjetura de Fulkerson são apresentados, enfatizando suas conexões com outras conjeturas. Um breve histórico do Problema das Quatro Cores e suas relações com snarks também são apresentados. Na segunda parte deste trabalho, a Conjetura de Fulkerson é verificada para algumas famílias infinitas de snarks construídas com o método de Loupekine, utilizando subgrafos do Grafo de Petersen. Primeiramente, mostramos que a família dos LP0-snarks satisfaz a Conjetura de Fulkerson. Em seguida, generalizamos este resultado para a família mais abrangente dos LP1-snarks. Além disto, estendemos estes resultados para Snarks de Loupekine construídos com subgrafos de snarks diferentes do Grafo de Petersen / Abstract: In 1971, Fulkerson proposed a conjecture that states that every bridgeless cubic graph has six perfect matchings such that each edge of the graph belongs to precisely two of these matchings. Fulkerson's Conjecture has been challenging researchers since its publication. It is easily verified for 3-edge-colourable cubic graphs. Therefore, the difficult task is to settle the conjecture for non-3-edge-colourable bridgeless cubic graphs, called snarks. In this dissertation, Fulkerson's Conjecture and snarks are presented with emphasis in their history and remarkable results. We selected some results related to Fulkerson's Conjecture, emphasizing their reach and connections with other conjectures. It is also presented a brief history of the Four-Colour Problem and its connections with snarks. In the second part of this work, we verify Fulkerson's Conjecture for some infinite families of snarks constructed with Loupekine's method using subgraphs of the Petersen Graph. More specifically, we first show that the family of LP0-snarks satisfies Fulkerson's Conjecture. Then, we generalise this result by proving that Fulkerson's Conjecture holds for the broader family of LP1-snarks. We also extend these results to even more general Loupekine Snarks constructed with subgraphs of snarks other than the Petersen Graph / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Abstract The next-generation networks are set to support a high data rate, low latency, high reliability, and diverse types of services and use cases. These requirements come at the expense of a more complex network management, and asymmetric and time-varying traffic dynamics. Accordingly, future networks will operate at different duplexing modes and with multiple access techniques. This thesis proposes novel transmission strategies and methodologies to dynamically optimize the duplexing modes and allocate resources for small cell based cellular networks. The first part of the thesis studies dynamic time-division-duplex (TDD) operation in dynamic and asymmetric uplink (UL) and downlink (DL) traffic conditions. In this regard, we propose a dynamic TDD framework that optimizes the UL and DL frame configuration and power allocation. Due to the high interference coupling between neighboring small cells, we propose a load-aware clustering method that groups the small cell base stations (SBSs) based on their spatial and load similarities. To balance the UL and DL loads within each cluster, we study the potential of load-based UL/DL decoupled user association in balancing the traffic loads within clusters. In the second part, we study the problem of half-duplex (HD)/full-duplex (FD) mode selection and UL/DL resource and power optimization in small cell networks. Therein, SBSs operate in non-orthogonal multiple access (NOMA) in both UL and DL to schedule multiple users at the same time-frequency resource. The goal of the study is therefore to select the optimal duplexing and multiple access scheme, based on the traffic load and interference conditions, such that users’ data rates are maximized, while stabilizing traffic queues. Finally, the last part of the thesis looks beyond rate maximization and focuses on ensuring low latency and high reliability in small cell networks providing edge computing services. The problem of distributing wireless resources to users requesting edge computing tasks is cast as a delay minimization problem under stringent reliability constraints. The study investigates the role of proactive computing in ensuring low latency edge computing, while the concept of hedged requests is presented as an enabler for computing service reliability. / Tiivistelmä Seuraavan sukupolven verkot suunnitellaan tukemaan suuria tiedonsiirtonopeuksia, pientä latenssia, erinomaista luotettavuutta ja monentyyppisiä palveluja ja käyttötapauksia. Näiden vaatimusten täyttämisen kääntöpuolena ovat entistä monimutkaisemmat verkonhallintatoiminnot sekä epäsymmetrinen ja ajallisesti muuttuva dataliikenteen dynamiikka. Verkot toimivat tulevaisuudessa eri dupleksointitiloissa hyödyntämällä useita eri liittymätekniikoita. Tässä tutkielmassa ehdotetaan uusia siirtostrategioita ja menetelmiä dupleksointitilojen dynaamista optimointia ja resurssien allokointia varten piensoluperustaisissa solukkoverkoissa. Tutkielman alkuosassa tarkastellaan dynaamisen aikajakodupleksin (TDD) toimintaa dataliikenneympäristöissä, joissa on käytössä dynaaminen ja epäsymmetrinen lähetysyhteys (UL) ja laskeva siirtotie (DL). Ehdotamme tältä osin dynaamista TDD-kehystä, joka optimoi UL- ja DL-kehyksen konfiguroinnin ja tehon allokoinnin. Vierekkäisten pienten solujen välisten kytkösten suuren interferenssin takia ehdotamme kuormituksen huomioivaa klusterointimenetelmää, jossa piensolutukiasemat (SBS) ryhmitellään niiden tilallisten ja kuormitusominaisuuksien yhteneväisyyden perusteella. Tutkimme UL- ja DL-kuormitusten tasapainottamista kussakin klusterissa tarkastelemalla UL/DL-yhteyksistä irti kytketyn, kuormitukseen perustuvan käyttäjän yhdistämisen mahdollisuuksia dataliikennekuormituksen tasapainottamisessa. Tutkielman toisessa osassa tarkastellaan puolidupleksi (HD)- ja kaksisuuntaisen (FD) -tilan valinnan ongelmaa ja UL-/DL-resurssien ja tehon optimointia piensoluverkoissa. Siinä piensolutukiasemat toimivat ei-ortogonaalisessa moniliittymässä (NOMA) sekä UL- että DL-yhteyksissä useiden käyttäjien ajoittamiseksi samalle aika-taajuusresurssille. Tutkielman tavoitteena on siten valita optimaalinen dupleksointi- ja moniliittymäkaavio dataliikenteen kuormituksen ja interferenssin perusteella siten, että käyttäjän tiedonsiirtonopeudet voidaan maksimoida ja dataliikennejonot tasata. Lopuksi tutkielman viimeisessä osassa tarkastellaan tiedonsiirtonopeuden maksimoinnin lisäksi pienen latenssin ja suuren luotettavuuden varmistamista piensoluverkoissa, jotka tuottavat reunalaskentapalveluja. Langattomien resurssien jakelemista käyttäjille, jotka vaativat reunalaskentatehtäviä, käsitellään viiveen minimoinnin ongelmana soveltamalla tiukkoja luotettavuusrajoituksia. Tutkielmassa tarkastellaan proaktiivisen tietojenkäsittelyn roolia pienen latenssin reunalaskennassa.