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.

網路技術發展的日新月異帶領了眾多新網路服務的崛起，例如即時影音串流這類的多媒體服務。但即時影音串流服務所產生的龐大資料流和傳輸延遲時間的嚴格限制也隨之而來的為網路環境帶來許多挑戰，在這些條件下，傳統Server-client拓樸架構將client要求的影音資料以單一鏈結傳輸時，常會因為頻寬不足而面臨嚴重的封包遺失，或是資料流擁擠造成的額外傳輸延遲使得封包無法達到即時性的需求。P2P網路擁有server-client架構所難以達到的規模伸縮性，且對於節點、鏈結失效所引起的傳輸錯誤也較能容忍，更重要的是，它有效的分散了原本負載在少數link上的龐大資料流。因此P2P架構近年來風行於即時影音串流服務。 目前P2P網路的拓樸多是隨意形成，當網路成員規模龐大時，由傳送端出發到遠方的接收端，途中可能經過無數的鏈結，每一個鏈結都會由於頻寬的不足使得資料流遭受某種程度的品質損害，另一方面，對即時影音服務而言，若資料流的累積延遲時間超出可容忍範圍時，無法為使用者接受。 本研究嘗試找出一個較好的拓樸用以傳輸多媒體資料流，使得位於最遠端節點的累積延遲亦能為使用者接受，且資料品質的損害程度最小。我們將之建置成一NP-Complete複雜度的問題模型，名為MLDST。而解法則是修改Dijkstra single-source shortest-path演算法，並加上每個節點承擔下游節點數量及延遲時間限制而來。我們以PlanetLab環境在實際的網路上進行實驗，證實我們的演算法比傳統的Minimum-Spanning Tree及shortest path spanning tree有更好的影像品質。 / Numerous new network services arise with the advanced development of network technologies, such as real-time multimedia streaming services. But challenges to network environment come along with the enormous traffic of data flows and rigorous restriction to transmission delay of real-time multimedia streaming services. Under this circumstance, conventional server-client topology suffers from serious packet loss and packet delay due to the overload of servers and their accessing links. Also, extra transmission delay may make packets fail to meet the requirement of real-timed services. Peer-to-peer network is more scalable than server-client model, and is much more tolerable to the transmission errors caused by node or link failures. More importantly, it effectively distributes load from the server to peers. As a consequence, peer-to-peer service architecture becomes very popular for real-time multimedia streaming services recently. Peer-to-peer networks are mostly formed in random fashion. As the size of network grows, packets may have to travel through numerous links to reach far-end receivers. The quality of data may be damaged by insufficient bandwidth of links. For real-time multimedia services, it is not acceptable to users if the cumulated packet delay exceeds a tolerable limit. Our research is trying to find a better topology to transmit multimedia data flows which makes the cumulated delay of the most-far-end user be tolerable and the damage of data quality is minimized. The problem is modeled as a MLDST problem, which is a NP-Complete problem. To solve the problem, we modified Dijkstra’s single-source shortest-path algorithm by bounding the node degree and adding delay constraint. The experiments were carried out on real network environment through PlanetLab. Experiments show that our algorithm outperforms traditional MST and shortest path spanning tree.

The Diameter-Constrained Minimum Spanning Tree Problem seeks a least cost spanning tree subject to a (diameter) bound imposed on the number of edges in the tree between any node pair. A traditional multicommodity flow model with a commodity for every pair of nodes was unable to solve a 20-node and 100-edge problem after one week of computation. We formulate the problem as a directed tree from a selected central node or a selected central edge. Our model simultaneously finds a central node or a central edge and uses it as the source for the commodities in a directed multicommodity flow model with hop constraints. The new model has been able to solve the 20-node, 100-edge instance to optimality after less than four seconds. We also present model enhancements when the diameter bound is odd (these situations are more difficult). We show that the linear programming relaxation of the best formulations discussed in this paper always give an optimal integer solution for two special, polynomially-solvable cases of the problem. We also examine the Diameter Constrained Minimum Steiner Tree problem. We present computational experience in solving problem instances with up to 100 nodes and 1000 edges. The largest model contains more than 250,000 integer variables and more than 125,000 constraints.

In this thesis, we make some contributions at the interface between algebra and graph theory. In Chapter 1, we give an overview of the topics and also the definitions and preliminaries. In Chapter 2, we estimate the number of possible types degree patterns of k-lacunary polynomials of degree t < p which split completely modulo p. The result is based on a rather unusual combination of two techniques: a bound on the number of zeros of lacunary polynomials and a bound on the so-called domination number of a graph. In Chapter 3, we deal with the determinant of bipartite graphs. The nullity of a graph G is the multiplicity of 0 in the spectrum of G. Nullity of a (molecular) graph (e.g., a bipartite graph corresponding to an alternant hydrocarbon) has important applications in quantum chemistry and Huckel molecular orbital (HMO) theory. A famous problem, posed by Collatz and Sinogowitz in 1957, asks to characterize all graphs with positive nullity. Clearly, examining the determinant of a graph is a way to attack this problem. In this Chapter, we show that the determinant of a bipartite graph with at least two perfect matchings and with all cycle lengths divisible by four, is zero. In Chapter 4, we first introduce an application of spectral graph theory in proving trigonometric identities. This is a very simple double counting argument that gives very short proofs for some of these identities (and perhaps the only existed proof in some cases!). In the rest of Chapter 4, using some properties of the well-known Chebyshev polynomials, we prove some theorems that allow us to evaluate the number of spanning trees in join of graphs, Cartesian product of graphs, and nearly regular graphs. In the last section of Chapter 4, we obtain the number of spanning trees in an (r,s)-semiregular graph and its line graph. Note that the same results, as in the last section, were proved by I. Sato using zeta functions. But our proofs are much shorter based on some well-known facts from spectral graph theory. Besides, we do not use zeta functions in our arguments. In Chapter 5, we present the conclusion and also some possible projects.

This dissertation considers a subclass of sum-of-ratios fractional combinatorial optimization problems (FCOPs) whose linear versions admit polynomial-time exact algorithms. This topic lies in the intersection of two scarcely researched areas of fractional programming (FP): sum-of-ratios FP and combinatorial FP. Although not extensively researched, the sum-of-ratios problems have a number of important practical applications in manufacturing, administration, transportation, data mining, etc. Since even in such a restricted research domain the problems are numerous, the main focus of this dissertation is a mathematical programming study of the three, probably, most classical FCOPs: Minimum Multiple Ratio Spanning Tree (MMRST), Minimum Multiple Ratio Path (MMRP) and Minimum Multiple Ratio Cycle (MMRC). The first two problems are studied in detail, while for the other one only the theoretical complexity issues are addressed. The dissertation emphasizes developing solution methodologies for the considered family of fractional programs. The main contributions include: (i) worst-case complexity results for the MMRP and MMRC problems; (ii) mixed 0-1 formulations for the MMRST and MMRC problems; (iii) a global optimization approach for the MMRST problem that extends an existing method for the special case of the sum of two ratios; (iv) new polynomially computable bounds on the optimal objective value of the considered class of FCOPs, as well as the feasible region reduction techniques based on these bounds; (v) an efficient heuristic approach; and, (vi) a generic global optimization approach for the considered class of FCOPs. Finally, extensive computational experiments are carried out to benchmark performance of the suggested solution techniques. The results confirm that the suggested global optimization algorithms generally outperform the conventional mixed 0{1 programming technique on larger problem instances. The developed heuristic approach shows the best run time, and delivers near-optimal solutions in most cases.

­^¤åºK­n Today¡AIC products have become a essential in the human life. Take the daily life of Taiwan¡¦s people for example, people use the IC products in every minutes: mobile phone, credit card, health insurance card, etc. The competition between IC products also has been a vital war for the company to protect its market position. Time to market for the IC product has also become more and more important for the company to maintain or even survive. More powerful performance of the IC product rely on more professional marketing position forecast, innovated design and time to market manufacturing. To realize a IC product come from the manufacturing through the IC design house, foundry and the package. There should be with different expertise between the companies or inside the company. How to make sure with correct manufacturing through these expertise to meet the time-to-marketing challenge is very important, especially, right people in right position. What¡¦s the role-play for the people during the manufacturing between and within the company/groups will be the focus in this thesis. Take the example for a semiconductor manufacturing company, there are divided with different functions of department. Each department has its own knowledge-based function to maintain or develop the related knowledge for a IC manufacturing. People should do the knowledge transfer inside the department and, moreover, the related functions with other departments. How do improve the efficiency through the effective communication and knowledge sharing will be discussed. The main results of this thesis are as the below 1. There are with built-up boundary between different groups/department organization due to its different job functions and expertise. It will be resulted as the communication barrier or knowledge transfer problem between these groups/organization even their goal is the same. 2. 5 categories can be identified for these barriers on the knowledge transfer and communication between different expertises. 3. Defined SOP(standard operation procedure) to communicate through documents and intensive discussion meeting can be improved to effective for the knowledge transfer between different groups/department organization, especially for the fresh engineers. 4. The psychological factor of human between different groups/organization is found to be another issue to block the knowledge transfer. How to eliminate the factor can be next study focus.

Thesis (Ph. D.)--Carnegie Mellon University, 2003. / Title from PDF title page (viewed Dec. 18, 2009). Includes bibliographical references (p. 49-52).

Thesis (M.S.)--Kent State University, 2009. / Title from PDF t.p. (viewed Jan. 25, 2010). Advisor: Feodor Dragan. Keywords: greedy routing. Includes bibliographical references (p. 76-77).

No description available.

No description available.