Muitos problemas de otimização em grafos, em especial problemas métricos, são mais fáceis de resolver em árvores. Portanto, uma estratégia para obter um bom algoritmo para certos problemas é obter uma árvore que aproxime o grafo, e utilizar uma solução do problema nessa árvore como uma solução aproximada para o problema no grafo original. Neste trabalho é estudada a técnica de Fakcharoenphol, Rao e Talwar, que mostraram como aproximar uma métrica finita arbitrária com n pontos por uma métrica numa árvore com distorção esperada O(lg n) -- o ótimo assintótico. Essa estratégia resulta em algoritmos de aproximação com boas razões de aproximação, e em algoritmos com bom fator de competitividade para diversos problemas de otimização online e distribuídos. É apresentada especificamente a aplicação da técnica ao problema do emparelhamento mínimo bipartido online, que ilustra como a aproximação de métricas auxilia na resolução de um problema e os cuidados que devem ser tomados nessa aplicação. / Many optimization problems on graphs, especially metric problems, are easier to solve on trees. Therefore, a strategy for obtaining a good algorithm for certain problems is to obtain a tree that approximates the graph, and use a solution of the problem on the tree as an approximate solution for the problem on the original graph. We study the work of Fakcharoenphol, Rao e Talwar, who showed how to approximate an arbitrary finite metric on n points by a tree metric with expected distortion O(lg n), which is asymptotically optimum. This strategy leads to algorithms with good approximation factors, and to competitive algorithms for various optimization problems, some of them online and distributed. Here, we present the application of that technique to the problem of finding a minimum online matching on a bipartite metric graph. This problem illustrates how metric approximation aids in solving a problem, and the care that must be taken when doing such an application.

<div>A central issue in systems engineering is to design systems where the stakeholders do not behave as expected by the systems designer. Usually, these stakeholders have different and often conflicting objectives. The stakeholders try to maximize their individual objective and the overall system do not function as expected by the systems designers.</div><div><br></div><div><div>We specifically study two such systems- a) cloud-based design and manufacturing system (CBDM) and b) Air Transportation System (ATS). In CBDM, two stakeholders</div><div>with conflicting objectives are designers trying to get their parts printed at the lowest possible price and manufacturers trying to sell their excess resource capacity at maximum prots. In ATS, on one hand, airlines make route selection decision with the goal of maximizing their market share and prots and on the other hand regulatory bodies such as Federal Aviation Administration tries to form policies that increase overall welfare of the people.</div></div><div><br></div><div><div>The objective in this dissertation is to establish a mechanism design based framework: a) for resource allocation in CBDM, and b) to guide the policymakers in channeling the evolution of network topology of ATS.</div></div><div><br></div><div><div>This is the rst attempt in literature to formulate the resource allocation in CBDM as a bipartite matching problem with designers and manufacturers forming two distinct set of agents. We recommend best mechanisms in different CBDM scenarios like totally decentralized scenario, organizational scenario etc. based on how well the properties of the mechanism meet the requirements of that scenario. In addition to analyzing existing mechanisms, CBDM offers challenges that are not addressed in the literature. One such challenge is how often should the matching mechanism be implemented when agents interact over a long period of time. We answer this question through theoretical propositions backed up by simulation studies. We conclude that a matching period equal to the ratio of the number of service providers to the arrival rate of designers is optimal when service rate is high and a matching period equal to</div><div>the ratio of mean printing time to mean service rate is optimal when service rate is low.</div></div><div><br></div><div><div>In ATS, we model the evolution of the network topology as the result of route selection decisions made by airlines under competition. Using data from historic decisions we use discrete games to model the preference parameters of airlines towards explanatory variables such as market demand and operating cost. Different from the existing literature, we use an airport presence based technique to estimate these parameters. This reduces the risk of over-tting and improves prediction accuracy. We conduct a forward simulation to study the effect of altering the explanatory variables on the Nash equilibrium strategies. Regulatory bodies could use these insights while forming policies.</div></div><div><br></div><div><div>The overall contribution in this research is a mechanism design framework to design complex engineered systems such as CBDM and ATS. Specically, in CBDM a matching mechanism based resource allocation framework is established and matching mechanisms are recommended for various CBDM scenarios. Through theoretical and</div><div>simulation studies we propose the frequency at which matching mechanisms should be implemented in CBDM. Though these results are established for CBDM, these</div><div>are general enough to be applied anywhere matching mechanisms are implemented multiple times. In ATS, we propose an airport presence based approach to estimate</div><div>the parameters that quantify the preference of airlines towards explanatory variables.</div></div>

The cutwidth of different graphs is a topic that has been extensively studied. The basis of this paper is the cutwidth of complete n-partite graphs. While looking at the cutwidth of complete n-partite graphs, we strictly consider the linear embedding and cyclic embedding. The relationship between the linear cutwidth and the cyclic cutwidth is discussed and used throughout multiple proofs of different cases for the cyclic cutwidth. All the known cases for the linear and cyclic cutwidth of complete bipartite, complete tripartite, and complete n-partite graphs are highlighted. The main focus of this paper is to expand on the cyclic cutwidth of complete tripartite graphs. Using the relationship of the linear cutwidth and cyclic cutwidth of any graph, we find a lower bound and an upper bound for the cyclic cutwidth of complete tripartite graph K_(r,r,pr) where r is odd and p is a natural number. Throughout this proof there are two cases that develop, p even and p odd. Within each case we have to consider the cuts of multiple regions to find the maximum cut of the cyclic embedding. Once all regions within each case are considered, we discover that the upper and lower bounds are equivalent. This discovery of the cyclic cutwidth of complete tripartite graph K_(r,r,pr) where r is odd and p is a natural number results in getting one step closer to finding the cyclic cutwidth of any complete tripartite graph K_(r,s,t).

This doctoral research explores the implications for the employment relationship of the intersection between employment relations and customer relations. The context for the research is Australian higher education - specifically those university workplaces which are strongly market focused and where resourcing is inadequate to meet customer expectations. Traditionally, serving one's customer has meant providing goods or services (as requested by the customer) and doing so with courtesy (as defined by social custom). The customer was clearly outside the traditional employment relationship between employer and employee, although a focus of its output. However, in the context of post-Fordist production systems and post-modern values including the rise of consumption, there has occurred an intersection of product and labour markets which has led to changes to the employment relationship and the labour process. The thesis answers the questions: In higher education, does the student-as-customer have significant influence on the organisation of work? If so, does this constitute a reconfigured model of the employment relationship? The rationale for re-examining the employment relationship in the context of changing consumption patterns lies in the search for more extensive explanations of factors which influence the labour process with the suggestion that consumption is of increasing relevance for industrial relations theory and practice (see for example Heery 1993; Frenkel, Korczynski, Shire and Tam 1999a). The growth of a culture of consumption and changing consumption patterns are symptomatic of change which is central to the Australian economy as a whole and to higher education in particular (Usher, Bryant and Johnson 1997; Scott 1995a). In this context the doctoral research explores the social relations involved in the process of Australian higher education as a service encounter. It examines the implications for the organisation of work in particular, and the traditional bipartite employment relationship in general (between employer and employee although it is noted that the state has a peripheral role), of the student's newly constructed status of customer. The research focus is on flexible delivery which is seen as a key strategic response by higher education institutions to meet their perceptions of their customers' needs and wants. Flexible delivery is a pedagogy, a marketing tool and a form of work organisation and is a fertile domain within which to seek the intersection of employment relations and customer relations. In keeping with the labour process ethnographic tradition, this research employs Burawoy's (1991) methodology of Extended Case Method. This doctoral research raises critical issues related to the incongruence between current Australian national research ethics regimes and long established ethnographic methods employing participant observation. The practical consequences of the national research ethics regime for empirical research are explored in the concluding chapter. The data identifies that university managements' preoccupation with customer relations has undermined the traditional employment relationship between employing institution and academic. While the academic employee in the service encounter is engaged in the primary relationship of the bipartite employment relationship, management's incorporation of the student-customer into formal organisational processes which may lead to control over the organisation of work, potentially brings into being a tripartite employment relationship between employee/employer/customer. In such a model, customer relations is no longer merely the output of the employment relationship but a process within it, with customers acting as management's agents of control. This thesis introduces the concept of the customer as partial-employer. The thesis findings challenge the current management paradigm of customer focus as a 'win-win' situation. In Australian higher education customer focused strategies have emerged from managerial assumptions about student-customer needs and wants, specifically those of flexibility and value-for-money. The unintended consequence of these assumptions on the academic labour process has been a significant shift in the balance of power between academic educator and student at the level of the service encounter, with the subjugation of traditional academic authority to the power of the consumer in what has become a market relationship.

With rapid growth of information on the Web, Web search engines have gained great momentum for exploiting valuable Web resources. Although keywords-based Web search engines provide relevant search results in response to users’ queries, future enhancement is still needed. Three important issues include (1) search results can be diverse because ambiguous keywords in queries can be interpreted to different meanings; (2) indentifying keywords in long queries is difficult for search engines; and (3) generating query-specific Web page summaries is desirable for Web search results’ previews. Based on clickthrough data, this thesis proposes a query-concept bipartite graph for representing queries’ relations, and applies the queries’ relations to applications such as (1) personalized query suggestions, (2) long queries Web searches and (3) query-specific Web page summarization. Experimental results show that query-concept bipartite graphs are useful for performance improvement for the three applications.

A theorem of Edmonds characterizes when a pair of matroids has a common basis. Enumerating the common bases of a pair of matroid is a much harder problem, and includes the #P-complete problem of counting the number of perfect matchings in a bipartite graph. We focus on the problem of counting the common bases in pairs of regular matroids, and describe a class called <i>Pfaffian matroid pairs</i> for which this enumeration problem can be solved. We prove that when a pair of regular matroids is non-Pfaffian, there is a set of common bases which certifies this, and that the number of bases in the certificate is linear in the size of the ground set of the matroids. When both matroids in a pair are series-parallel, we prove that determining if the pair is Pfaffian is equivalent to finding an edge signing in an associated graph, and in the case that the pair is non-Pfaffian, we obtain a characterization of this associated graph. Pfaffian bipartite graphs are a class of graphs for which the number of perfect matchings can be determined; we show that the class of series-parallel Pfaffian matroid pairs is an extension of the class of Pfaffian bipartite graphs. Edmonds proved that the polytope generated by the common bases of a pair of matroids is equal to the intersection of the polytopes generated by the bases for each matroid in the pair. We consider when a similar property holds for the binary space, and give an excluded minor characterization of when the binary space generated by the common bases of two matroids can not be determined from the binary spaces for the individual matroids. As a result towards a description of the lattice of common bases for a pair of matroids, we show that the lattices for the individual matroids determine when all common bases of a pair of matroids intersect a subset of the ground set with fixed cardinality.

A theorem of Edmonds characterizes when a pair of matroids has a common basis. Enumerating the common bases of a pair of matroid is a much harder problem, and includes the #P-complete problem of counting the number of perfect matchings in a bipartite graph. We focus on the problem of counting the common bases in pairs of regular matroids, and describe a class called <i>Pfaffian matroid pairs</i> for which this enumeration problem can be solved. We prove that when a pair of regular matroids is non-Pfaffian, there is a set of common bases which certifies this, and that the number of bases in the certificate is linear in the size of the ground set of the matroids. When both matroids in a pair are series-parallel, we prove that determining if the pair is Pfaffian is equivalent to finding an edge signing in an associated graph, and in the case that the pair is non-Pfaffian, we obtain a characterization of this associated graph. Pfaffian bipartite graphs are a class of graphs for which the number of perfect matchings can be determined; we show that the class of series-parallel Pfaffian matroid pairs is an extension of the class of Pfaffian bipartite graphs. Edmonds proved that the polytope generated by the common bases of a pair of matroids is equal to the intersection of the polytopes generated by the bases for each matroid in the pair. We consider when a similar property holds for the binary space, and give an excluded minor characterization of when the binary space generated by the common bases of two matroids can not be determined from the binary spaces for the individual matroids. As a result towards a description of the lattice of common bases for a pair of matroids, we show that the lattices for the individual matroids determine when all common bases of a pair of matroids intersect a subset of the ground set with fixed cardinality.

We propose an object-based multimedia model for specifying the QoS (quality of service) requirements, such as the maximum data-dropping rate or the maximum data-delay rate. We also present a resource allocation model, called the net-profit model, in which the satisfaction of user¡¦s QoS requirements is measured by the benefit earned by the system. Based on the net-profit model, the system is rewarded if it can allocate enough resources to a multimedia delivery request and fulfill the QoS requirements specified by the user. At the same time, the system is penalized if it cannot allocate enough resources to a multimedia delivery request. In this dissertation, we present our research in developing optimal solutions for multimedia stream delivery in bandwidth limited networks. To fulfill the QoS requirements, the resource, such as bandwidth, should be reserved in advance. Hence, we first investigate how to allocate a resource such that the QoS satisfaction is maximized, assuming that the QoS requirements are given a priori. The proposed optimal solution has significant improvement over the based line algorithm, EDF (Earliest Deadline First). Among all the optimal solutions found from the above problem, the net-profit may be distributed unevenly among the multimedia delivery requests. Furthermore, we tackle the fairness problem -- how to allocate a resource efficiently so that the difference of the net-profit between two requests is minimized over all the possible optimal solutions of the maximum total net-profit. A dynamic programming based algorithm is proposed to find all the possible optimal solutions and, in addition, three filters are conducted to improve the efficiency of the proposed algorithm. The experimental results show that the filters prune out unnecessary searches and improve the performance significantly, especially when the number of tasks increases. For some multimedia objects, they might need to be delivered in whole, indivisible, so we extend the proposed multimedia object-based model to indivisible objects. A dynamic programming based algorithm is presented to find an optimal solution of the delivery problem, where the total net-profit is maximized.

This thesis investigates new clustering paradigms and algorithms based on the principle of the shared nearest-neighbors (SNN. As most other graph-based clustering approaches, SNN methods are actually well suited to overcome data complexity, heterogeneity and high-dimensionality.The first contribution of the thesis is to revisit existing shared neighbors methods in two points. We first introduce a new SNN formalism based on the theory of a contrario decision. This allows us to derive more reliable connectivity scores of candidate clusters and a more intuitive interpretation of locally optimum neighborhoods. We also propose a new factorization algorithm for speeding-up the intensive computation of the required sharedneighbors matrices.The second contribution of the thesis is a generalization of the SNN clustering approach to the multi-source case. Whereas SNN methods appear to be ideally suited to sets of heterogeneous information sources, this multi-source problem was surprisingly not addressed in the literature beforehand. The main originality of our approach is that we introduce an information source selection step in the computation of candidate cluster scores. As shown in the experiments, this source selection step makes our approach widely robust to the presence of locally outlier sources. This new method is applied to a wide range of problems including multimodal structuring of image collections and subspace-based clustering based on random projections. The third contribution of the thesis is an attempt to extend SNN methods to the context of bipartite k-nn graphs. We introduce new SNN relevance measures revisited for this asymmetric context and show that they can be used to select locally optimal bi-partite clusters. Accordingly, we propose a new bipartite SNN clustering algorithm that is applied to visual object's discovery based on a randomly precomputed matching graph. Experiments show that this new method outperformed state-of-the-art object mining results on OxfordBuilding dataset. Based on the discovered objects, we also introduce a new visual search paradigm, i.e. object-based visual query suggestion.

The one- and two-sided bipartite graph drawing problem alms to find a layout of a bipartite graph, with vertices of the two parts placed on parallel imaginary lines, that has the minimum number of edge-crossings. Vertices of one part are in fixed positions for the one-sided problem, whereas all vertices are free to move along their lines in the two-sided version. Many different heuristics exist for finding approximations to these problems, which are NP-hard. New sequential and parallel methods for producing drawings with low edgecrossings are investigated and compared to existing algorithms, notably Penalty Minimisation and Sifting, the current leaders. For the one-sided problem, new methods that include those based on simple stochastic hillclimbing, simulated annealing and genet.ic algorithms were tested. The new block-crossover genetic algorithm produced very good results with lower crossings than existing methods, although it tended to be slower. However, time was a secondary aim, the priority being to achieve low numbers of crossings. This algorithm can also be seeded with the output of an existing algorithm to improve results; combining with Penalty Minimisation in this way improved both the speed and number of crossings. Four parallel methods for the one-sided problem have been created, although two were abandoned because they gave bad results for even simple graphs. The other two methods, based on stochastic hill-climbing, produced acceptable results in faster times than similar sequential methods. PVM was used as the parallel communication system. Two new heuristics were studied for the two-sided problem, for which the only known existing method is to apply one-sided algorithms iteratively. The first is based on a heuristic for the linear arrangment problem; the second is a method of performing stochastic hill-climbing on two sides. A way of applying anyone-sided algorithm iteratively was also created. The linear arrangement method based on the Koren-Harel multi-scale algorithm achieved the best results, outperforming iterative Barycentre (previously the best method) and iterative Penalty Minimisation. Another area of this work created three new heuristics for the k-planar drawing problem where k > 1. These are the first known practical algorithms to solve this problem. A sequential genetic algorithm based on TimGA is devised to work on k-planar graphs. Two parallel algorithms, one island model and the other a 'mesh' model, are also given. Comparison of results for k = 2 indicate that the parallel island method is better than the other two methods. MPI was used for the parallel communication. Overall, 14 new methods are introduced, of which 10 were developed into working algorithms. For the one-sided bipartite graph drawing problem the new block-crossover genetic algorithm can produce drawings with lower crossings than the current best available algorithms. The parallel methods do not perform as well as the sequential ones, although they generally achieved the same results faster. All of the new two-sided methods worked well; the weighted two-sided swap stochastic hill-climbing method was comparable to the existing best method, iterative Barycentre, and generally produced drawings with lower crossings, although it suffered with needing a good termination condition. The new methods based on the linear arrangement problem consistently produced drawings with lower crossings than iterative Barycentre, although they were nearly always slower. A new parallel algorithm for the k-planar drawing problem, based on the island model, generally created drawings with the lowest edge-crossings, although no algorithms were known to exist to make comparisons.