Studies On Algorithms For Combinatorial Optimization Problems

Combinatorial optimization has a long history with recent development. Some famous mathematicians, like Fermat, Euler, etc, distributed a lot to its founding and evolving. In the second half of the twentieth century, with the development of the industrial revolution and modern administration science, especially the fast development of computer technology and its broad application, combinatorial optimization has become an independent branch of computer science and operations research. Some problems and methods developed accidentally by mathematicians one hundred years ago, has taken a critical role in network communication, logistics management and strategy, traffic planning etc, which they never imagined. This situation also illustrates that combinatorial optimization is potentially important and useful.The goal of a combinatorial optimization problem is to find the optimal solution among all of its feasible solutions. Generally speaking, a combinatorial optimization problem can be stated as follows: LetΩ= {s₁, s₂,…, s_n} be the solution space of all states, C(S_i) be the function value of state s_i, we are asked to find the optimal solution s^*, such that C(s^*) = min{C(s_i)} holds for all s_i∈Ω.Typical combinatorial optimization problems include Travelling Salesman Problem, Knapsack Problem, Bin Packing Problem, Minimum Degree Spanning Tree Problem, Set Cover Problem, etc. These problems are seemingly simple, and closely related to engineering situations. However, it is hard for modern computers to solve them optimally. This is mainly because the algorithms for these problems need very long time and extremely huge memory. This is also known as "combinatorial explosion" and it is impractical for current computers to solve these problems. It is the usefulness and complexity of combinatorial optimization problems that inspire people to study the theories and algorithms for them.For combinatorial optimization problems, some of them belong to P class problems. Designing an algorithm for a problem in P class requires unraveling and characterizing its combinatorial properties as a first step. We then exploit the uncovered structure and develop an algorithm. Unfortunately, many important problems is NP-Complete, and hence it is hard to solve them exactly. When such problems scale beyond certain size, even supercomputer cannot solve them. This is also the long term project to be done in computer science. Efficiently solving these problems has significant effect on national economics and national defense constructions. Therefore, it is important to develop efficient algorithms for these problems for both theoretical and practical reasons.For NP-hard problems, people usually focus on finding a feasible suboptimal solution rather than an optimal one in a relatively short time (polynomial time). In fact, there is a vast body of literature on so-called heuristic algorithms for a large number of defferent applications. The main point of criticism with these heuristic algorithms is however, that there is no guarantee on the quality of the computed solution. In fact, for each given heuristic there are usually examples on which it performs poorly: The computed solution has a value which deviates from the optimum solution value by a large factor.In this paper, we define and introduce approximation algorithms which address the main weakness of heuristics of not being able to bound the quality of the computed solution.On the other hand, due to the hardness of NP-hard problems, randomization methods are introduced to deal with these problems. Generally speaking, randomized algorithm takes random numbers during its running. It is a breakthrough idea of designing algorithms, in contrast with traditional deterministic algorithms. Currently, this idea has been applied in many earas, such as number theory, computational geometry, graph theory, parallel computing, network routing, etc.We study the algorithms and their complexity of Low Degree Network Design Problem, Set Cover Problem and Planning Problem. These problems have strong root in many applications, such as computer network, communication protocol, etc. Planning is also applied in robot controlling. The main contributions of the thesis are as follows:1. The thesis proposes a polynomial exact algorithm for the minimum degree spanning tree problem in directed acyclic graphs.Consider the following scenario: We are given a computer nework connecting a server to a set of client hosts using intermediate switches. An application that runs on the server would like to send the same information from the server to each of the client hosts. One wishes to build a spanning tree that minimize the total cost of the network as well as the maximum work done by (that is, the degree of) any vertex. In terms of graph theory, the clients correspond to the vertices of the graph, the connection in the network correspond to the edges of the graph. The constraints are converted to those of the maximum degree of the vertices. Given an undirected graph G = (V, E), one want to find a spanning tree T such that the degree of T is minimal among all the spanning trees of G. This problem is NP-hard, since it is a generalization of Hamiltonian Path problem which is NP-hard. This thesis proposes a polynomial exact algorithm for the directed acyclic graph version of the minimum degree spanning tree problem. Then, we apply this method to the minimum time broadcast problem, and improve its previous algorithm.2. This thesis proposes an approximation algorithm for the bounded degree minimum spanning tree problem in directed acyclic graphs.The problem closely related to the MDST problem is the Minimum Degree Minimum Spanning Tree (MDMST) problem. In this weighted case, there is a nonnegtiave cost value associated with each edge in graph G, we are asked to find a minimum spanning tree T, such that its degree is the smallest among all minimum spanning trees of G. This problem has a large number of applications in network design, VLSI, etc. During network constructing, we not only want to reduce the work of each node (degree of the node), but also the overall cost of network construction (costs of edges). MDMST is a natural modeling of such competing needs.The buget version of the MDMST problem is the Bounded Degree Minimum Spanning Tree (BDMST) problem. Given a degree bound B≥1, the BDMST problem asks to find a spanning tree T, such that its degree is at most B.For the problems addressed above, there is a vast body of literature on the undirected cases, but very little on the directed cases. Part of this work is dedicated to the latter. We give an approximation algorithm that can make a tradeoff between degree and cost, which correspond to the two competing constraints in this problem,3. This thesis proposes a randomized approximation algorithm for the Set Cover problem.The Set Cover problem has many important applications in practice. It also has been one of the main problems for computer algorithm research. In contrast with the tradictional "deterministic" algorithms, we give a "randomized" algorithm for the Set Cover problem and analyze its expected performance. Due to its randomness, the solution outputted by the algorithm may differ from one run to another. Thus we can run it multiple times, and select the best solution from them. Moreover, the time complexity of this algorithm is linear, so it is practical for it to run several times.4. This thesis proposes a state-space reduction algorithm for planning.Planning is one of most important research areas in artificial intelligence. It has comprehensive applications, such as spaceflight technology, flight course arrangement, business strategy, medical optimization, autocontrol, engineering design, etc.State-space search is a fundamental and pervasive approach for AI. The state space is typically modeled as a directed graph. A cost can be associated with each edge in the graph and the search tries to identify the path with the minimum total cost from an initial state to a goal state.The performance of traditional state space search algorithms depend deadly on the accuracy of heuristic functions. However, as revealed by recent work, an admissible search with even almost perfect heuristics may still have exponential complexity. Hence, it is important to improve other components of the search algorithm that are orthogonal to the design of better heuristics. In this paper, we propose a completeness and optimality preserving reduction technique, the expansion core (EC) method. This method can reduce the original space to a smaller one without losing completeness and optimality. Moreover, this method can be combined with other search algorithms on planning domains to even more speed up search process.To further study the work started in this thesis, the author proposes the following future directions:1. Algorithms for the low degree network design problem in general directed graphs. For this problem we mainly study the special case of directed acyclic graph, general graph case is one of our future directions.2. Randomized algorithms for the set cover problem and its variations and duals. Dsigning randomized algorithms for these problems is our another future direction.3. Algorithms with more powerful reduction ability. State-space reduction is orthogonal to and can be conbined with heuristics. Due to the restrictions of heuristics, it's even more important to improve reduction ability.