O problema da árvore geradora de comunicação ótima recebe um grafo com comprimentos não negativos nas arestas e um requerimento não negativo entre cada par de vértices; sendo o objetivo encontrar uma árvore geradora do grafo que minimize o custo de comunicação, que é a soma sobre cada par de vértice da distância entre eles na árvore vezes o requerimento entre eles. Este problema é NP-difícil, assim como vários casos particulares dele. Neste trabalho estudamos algumas variantes deste problema, introduzimos novos casos particulares que são também NP-difíceis e propomos esquemas de aproximação polinomial para alguns deles. / The optimum communication spanning tree problem receives a graph with non-negative lengths over the edges and non-negative requirements for each pair of nodes; being the objective to find a spanning tree of the graph that minimizes the communication cost, which is given by the sum, over each pair of nodes, of the distance, in the tree, between the nodes multiplied by the requirement between them. This problem and several of its particular cases are NP-hard. In this work we study some of the variants, also we introduce new NP-hard particular cases of the problem and propose polynomial approximation schemes for some of them.

abstract: This thesis addresses the following fundamental maximum throughput routing problem: Given an arbitrary edge-capacitated n-node directed network and a set of k commodities, with source-destination pairs (s_i,t_i) and demands d_i> 0, admit and route the largest possible number of commodities -- i.e., the maximum throughput -- to satisfy their demands. The main contributions of this thesis are three-fold: First, a bi-criteria approximation algorithm is presented for this all-or-nothing multicommodity flow (ANF) problem. This algorithm is the first to achieve a constant approximation of the maximum throughput with an edge capacity violation ratio that is at most logarithmic in n, with high probability. The approach used is based on a version of randomized rounding that keeps splittable flows, rather than approximating those via a non-splittable path for each commodity: This allows it to work for arbitrary directed edge-capacitated graphs, unlike most of the prior work on the ANF problem. The algorithm also works if a weighted throughput is considered, where the benefit gained by fully satisfying the demand for commodity i is determined by a given weight w_i>0. Second, a derandomization of the algorithm is presented that maintains the same approximation bounds, using novel pessimistic estimators for Bernstein's inequality. In addition, it is shown how the framework can be adapted to achieve a polylogarithmic fraction of the maximum throughput while maintaining a constant edge capacity violation, if the network capacity is large enough. Lastly, one important aspect of the randomized and derandomized algorithms is their simplicity, which lends to efficient implementations in practice. The implementations of both randomized rounding and derandomized algorithms for the ANF problem are presented and show their efficiency in practice. / Dissertation/Thesis / Masters Thesis Computer Science 2020

<div>We consider the maximum vertex-weighted matching problem (MVM), in which non-negative weights are assigned to the vertices of a graph, and the weight of a matching is the sum of the weights of the matched vertices. Vertex-weighted matchings arise in many applications, including internet advertising, facility scheduling, constraint satisfaction, the design of network switches, and computation of sparse bases for the null space or the column space of a matrix. Let m be the number of edges, n number of vertices, and D the maximum degree of a vertex in the graph. We design two exact algorithms for the MVM problem with time complexities of O(mn) and O(Dmn). The new exact algorithms use a maximum cardinality matching as an initial matching, after which the weight of the matching is increased using weight-increasing paths.</div><div><br></div><div>Although MVM problems can be solved exactly in polynomial time, exact MVM algorithms are still slow in practice for large graphs with millions and even billions of edges. Hence we investigate several approximation algorithms for MVM in this thesis. First we show that a maximum vertex-weighted matching can be approximated within an approximation ratio arbitrarily close to one, to k/(k + 1), where k is related to the length of augmenting or weight-increasing paths searched by the algorithm. We identify two main approaches for designing approximation algorithms for MVM. The first approach is direct; vertices are sorted in non-increasing order of weights, and then the algorithm searches for augmenting paths of restricted length that reach a heaviest vertex. (In this approach each vertex is processed once). The second approach repeatedly searches for augmenting paths and increasing paths, again of restricted length, until none can be found. In this second, iterative approach, a vertex may need to be processed multiple times. We design two approximation algorithms based on the direct approach with approximation ratios of 1/2 and 2/3. The time complexities of the 1/2-approximation algorithm is O(m + n log n), and that of the 2/3-approximation algorithm is O(mlogD). Employing the second approach, we design 1/2- and 2/3-approximation algorithms for MVM with time complexities of O(Dm) and O(D²m), respectively. We show that the iterative algorithm can be generalized to nd a k/(k+1)-approximate MVM with a time complexity of O(D^km). In addition, we design parallel 1/2- and 2/3-approximation algorithms for a shared memory programming model, and introduce a new technique for locking augmenting paths to avoid deadlock and related problems. </div><div><br></div><div>MVM problems may be solved using algorithms for the maximum edge-weighted matching (MEM) by assigning to each edge a weight equal to the sum of the vertex weights on its endpoints. However, our results will show that this is one way to generate MEM problems that are difficult to solve. On such problems, exact MEM algorithms may require run times that are a factor of a thousand or more larger than the time of an exact MVM algorithm. Our results show the competitiveness of the new exact algorithms by demonstrating that they outperform MEM exact algorithms. Specifically, our fastest exact algorithm runs faster than the fastest MEM implementation by a factor of 37 and 18 on geometric mean, using two different sets of weights on our test problems. In some instances, the factor can be higher than 500. Moreover, extensive experimental results show that the MVM approximation algorithm outperforms an MEM approximation algorithm with the same approximation ratio, with respect to matching weight and run time. Indeed, our results show that the MVM approximation algorithm outperforms the corresponding MEM algorithm with respect to these metrics in both serial and parallel settings.</div>

We investigate diverse aspects of the performance of wireless networks, including throughput, delay and distributed complexity. <br />One of the main challenges for optimizing them arises from radio interference, an inherent factor in wireless networks.<br />Graph-based interference models represent a large class of interference models widely used for the study of wireless networks,<br />and suffer from the weakness of over-simplifying the interference caused by wireless signals in a local and binary way.<br />A more sophisticated interference model, the physical interference model, based on SINR constraints,<br />is considered more realistic but is more challenging to study (because of its non-linear form and non-local property).<br />In this dissertation, we study the connections between the two types of interference models -- graph-based and physical interference models --<br />and tackle a set of fundamental problems under the physical interference model;<br />previously, some of the problems were still open even under the graph-based interference model, and to those we have provided solutions under both types of interference models.<br /><br />The underlying interference models affect scheduling and power control -- essential building blocks in the operation of wireless networks -- that directly deal with the wireless medium; the physical interference model (compared to graph-based interference model) compounds the problem of efficient scheduling and power control by making it non-local and non-linear.<br />The system performance optimization and tradeoffs with respect to throughput and delay require a ``global\'\' view across<br />transport, network, media access control (MAC), physical layers (referred to as cross-layer optimization)<br />to take advantage of the control planes in different levels of the wireless network protocol stack.<br />This can be achieved by regulating traffic rates, finding traffic flow paths for end-to-end sessions,<br />controlling the access to the wireless medium (or channels),<br />assigning the transmission power, and handling signal reception under interference.<br /><br />The theme of the dissertation is<br />distributed algorithms and optimization of QoS objectives under the physical interference model.<br />We start by developing the first low-complexity distributed scheduling and power control algorithms for maximizing the efficiency ratio for different interference models;<br />we derive end-to-end per-flow delay upper-bounds for our scheduling algorithms and our delay upper-bounds are the first network-size-independent result known for multihop traffic.<br />Based on that, we design the first cross-layer multi-commodity optimization frameworks for delay-constrained throughput maximization by incorporating the routing and traffic control into the problem scope.<br />Scheduling and power control is also inherent to distributed computing of ``global problems\'\', e.g., the maximum independent set problems in terms of transmitting links and local broadcasts respectively, and the minimum spanning tree problems.<br />Under the physical interference model, we provide the first sub-linear time distributed solutions to the maximum independent set problems, and also solve the minimum spanning tree problems efficiently.<br />We develop new techniques and algorithms and exploit the availability of technologies (full-/half-duplex radios, fixed/software-defined power control) to further improve our algorithms.<br />%This fosters a deeper understanding of distributed scheduling from the network computing point of view.<br /><br /><br />We highlight our main technical contributions, which might be of independent interest to the design and analysis of optimization algorithms.<br />Our techniques involve the use of linear and mixed integer programs in delay-constrained throughput maximization. This demonstrates the combined use of different kinds of combinatorial optimization approaches for multi-criteria optimization.<br />We have developed techniques for queueing analysis under general stochastic traffic to analyze network throughput and delay properties.<br />We use randomized algorithms with rigorously analyzed performance guarantees to overcome the distributed nature of wireless data/control communications.<br />We factor in the availability of emerging radio technologies for performance improvements of our algorithms.<br />Some of our algorithmic techniques that would be of broader use in algorithms for the physical interference model include:<br />formal development of the distributed computing model in the SINR model, and reductions between models of different technological capabilities, the redefinition of interference sets in the setting of SINR constraints, and our techniques for distributed computation of rulings (informally, nodes or links which are well-separated covers).<br /> / Ph. D.

Cette thèse se focalise sur des algorithmes efficaces en énergie pour des problèmes d'ordonnancement de tâches sur des processeurs pouvant varier la vitesse d'exécution ainsi que sur des processeurs fonctionnant sous un mécanisme de réchauffement-refroidissement, où pour un budget d'énergie donné ou un seuil thermique, l'objectif consiste à optimiser un critère de Qualité de Service. Une partie de notre recherche concerne des problèmes d'ordonnancement de tâches apparaissant dans des environnements de traitement de grandes données. Dans ce contexte, nous nous focalisons sur le paradigme MapReduce en considérant des problèmes d'ordonnancement efficaces en énergie sur un ensemble de processeurs, ainsi que pour la version classique.Premièrement, nous proposons des résultats de complexité, des algorithmes optimaux et approchés pour différentes variantes du problème de la minimisation du retard maximal d'un ensemble de tâches sur un processeur pouvant varier la vitesse d'exécution. Ensuite, nous considérons le problème d'ordonnancement MapReduce dans les versions énergétique et classique sur des processeurs non-reliés où le but est de minimiser le temps d'achèvement pondéré. Nous étudions deux cas spéciaux et les généralisations de ces deux problèmes en proposant des algorithmes d'approximation constante. Enfin, nous étudions le problème d'ordonnancement dans lequel la température du processeur est en-dessous un seuil donné où chaque tâche contribue au réchauffement et le but est de maximiser le nombre de tâches exécutées. Nous considérons le cas où les tâches ont des durées unitaires et ayant la même date d'échéance et nous étudions le rapport d'approximation de ce problème. / This thesis is focused on energy-efficient algorithms for job scheduling problems on speed-scalable processors, as well as on processors operating under a thermal and cooling mechanism, where, for a given budget of energy or a thermal threshold, the goal is to optimize a Quality of Service criterion. A part of our research concerns scheduling problems arising in large-data processing environments. In this context, we focus on the MapReduce paradigm and we consider problems of energy-efficient scheduling on multiple speed-scalable processors as well as classical scheduling on a set of unrelated processors.First, we propose complexity results, optimal and constant competitive algorithms for different energy-aware variants of the problem of minimizing the maximum lateness of a set of jobs on a single speed-scalable processor. Then, we consider energy-aware MapReduce scheduling as well as classical MapReduce scheduling (where energy is not our concern) on unrelated processors, where the goal is to minimize the total weighted completion time of a set of MapReduce jobs. We study special cases and generalizations of both problems and propose constant approximation algorithms. Finally, we study temperature-aware scheduling on a single processor that operates under a strict thermal threshold, where each job has its own heat contribution and the goal is to maximize the schedule's throughput. We consider the case of unit-length jobs with a common deadline and we study the approximability of the problem.

京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第18621号 / 情博第545号 / 新制||情||96(附属図書館) / 31521 / 京都大学大学院情報学研究科数理工学専攻 / (主査)教授 永持 仁, 教授 太田 快人, 教授 髙橋 豊 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

Yes / In this paper, we report the results of our recent research into the understanding of the exact distribution of a smile across the face, especially the distinction in the weight distribution of a smile between a genuine and a posed smile. To do this, we have developed a computational framework for the analysis of the dynamic motion of various parts of the face during a facial expression, in particular, for the smile expression. The heart of our dynamic smile analysis framework is the use of optical flow intensity variation across the face during a smile. This can be utilised to efficiently map the dynamic motion of individual regions of the face such as the mouth, cheeks and areas around the eyes. Thus, through our computational framework, we infer the exact distribution of weights of the smile across the face. Further, through the utilisation of two publicly available datasets, namely the CK+ dataset with 83 subjects expressing posed smiles and the MUG dataset with 35 subjects expressing genuine smiles, we show there is a far greater activity or weight distribution around the regions of the eyes in the case of a genuine smile. / Supported in part by the European Union's Horizon 2020 Programme H2020-MSCA-RISE-2017, under the project PDE-GIR with grant number 778035.

We present an implementation of a very recent approximation algorithm for scheduling jobs on a single machine with precedence constraints, minimising the total weighted completion time. We also evaluate the performance of this implementation. The algorithm was published by Shi Li in 2021 and is a (6+ε)-approximation algorithm for the multiprocessor problem P|prec|∑j wjCj. We have implemented a version which is a (2+ε)-approximation algorithm for the single processor problem 1|prec|∑j wjCj. This special case can easily be generalised to the multiprocessor case, as the two algorithms are based on the same LP relaxation of the problem. Unlike other approximation algorithms for this and similar problems, for example, those published by Hall, Schulz, Shmoys and Wein in 1997, and by Li in 2020, this algorithm has been developed with a focus on obtaining a good asymptotic run time guarantee, rather than obtaining the best possible guarantee on the quality of solutions. Li’s algorithm has run time O((n+κ) · polylog(n+κ) · log3 pmax · 1/ε2), where n is the number of jobs, κ is the number of precedence constraints and pmax is the largest of the processing times of the jobs. We also present a detailed explanation of the algorithm aimed at readers who do not necessarily have a background in scheduling and/or approximation algorithms, based on the paper by Li. Finally, we empirically evaluate how well (our implementation of) this algorithm performs in practice. The performance was measured on a set of 96 randomly generated instances, with the largest instance having 1024 jobs and 32 768 precedence constraints. We can find a solution for an instance with 512 jobs and 11 585 precedence constraints in 25 minutes. / Vi presenterar en praktisk implementation av en ny approximationsalgoritm för schemaläggning av jobb på en maskin med ordningsbivillkor, under minimering av den viktade summan av sluttider. Algoritmen, som publicerades av Shi Li år 2021, är en (6+ε)-approximationsalgoritm för multiprocessorproblemet P|prec|∑j wjCj. Vi har implementerat en version som är en (2+ε)-approximationsalgoritm för enprocessorproblemet 1|prec|∑j wjCj. Detta specialfall kan enkelt generaliseras till multiprocessorfallet, eftersom de två algoritmerna baseras på samma LP-relaxation av problemet. Till skillnad från andra approximationsalgoritmer för detta och liknande problem, exempelvis de från Hall, Schulz, Shmoys och Wein år 1997, och från Li år 2020, har denna algoritm utvecklats med fokus på att uppnå en bra garanti på asymptotisk körtid, istället för att försöka uppnå den bästa möjliga garantin på lösningarnas kvalité. Lis algoritm har körtid O((n+κ) · polylog(n+κ) · log3 pmax · 1/ε2), där n är antalet jobb, κ antalet ordningsbivillkor och pmax är den största körtiden bland jobben. En detaljerad beskrivning av algoritmen riktad till personer som inte nödvändigtvis har förkunskaper inom schemaläggning och/eller approximationsalgoritmer, baserad på artikeln, ges också. Slutligen utvärderar vi empiriskt hur väl (vår implementation av) denna algoritm presterar i praktiken. Implementationens egenskaper mättes på en uppsättning av 96 slumplässigt genererade instanser, där den största instansen har 1024 jobb och 32768 ordningsbivillkor. Med vår implementation kan vi hitta en lösning för en instans med 512 jobb och 11 585 precedencensbivillkor på 25 minuter.

No description available.

No description available.