Access to abstract restricted until 05/2015. / Asscess to thesis restricted until 05/2015. / Department of Computer Science

Many geometry problems can be solved by transformation to graph problems. Often, both the geometry version and graph version of the problem are NP-hard - and therefore not likely to be solved in polynomial time. One approach to solving these hard problems is to use fixed parameter tractable (FPT) algorithms. We present a framework for developing FPT algorithms for graph problems using dynamic programming, monadic second order logic of graphs, tree-width, and bidimensionality. We use this framework to obtain FPT results for covering tour problems on grid-graphs with turn costs. The results for these problems are not practical, but they demonstrate how the basic framework can be used to quickly obtain FPT results. We provide suggestions on further research to improve our FPT results and to apply our framework to obtain new FPT results.

No description available.

by Chi-lok Chan. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1994. / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Scheduling Problems of Chain-like Task System --- p.4 / Chapter 2.1 --- Introduction --- p.4 / Chapter 2.2 --- Problem Assumptions and Notations Definition --- p.7 / Chapter 2.3 --- Related Works --- p.9 / Chapter 2.3.1 --- Bokhari's Algorithm --- p.10 / Chapter 2.3.2 --- Sheu and Chiang's Algorithm --- p.12 / Chapter 2.3.3 --- Hsu's Algorithm --- p.12 / Chapter 2.4 --- Decision Algorithms for Un-mergeable Task System --- p.18 / Chapter 2.4.1 --- Feasible Length-K Schedule --- p.18 / Chapter 2.4.2 --- Generalized Decision Test --- p.23 / Chapter 2.5 --- Dominated and Non-dominated Task Systems --- p.26 / Chapter 2.5.1 --- Algorithm for Dominated Task System --- p.26 / Chapter 2.5.2 --- Property of Non-dominated Task System --- p.27 / Chapter 2.6 --- A Searching-Based Algorithm for the Optimization Problem --- p.28 / Chapter 2.6.1 --- Algorithm --- p.29 / Chapter 2.6.2 --- Complexity Analysis --- p.31 / Chapter 2.7 --- A Searching Algorithm Based on a Sorted Matrix --- p.33 / Chapter 2.7.1 --- Sorted Matrix --- p.33 / Chapter 2.7.2 --- Algorithm for the Optimization Problem --- p.35 / Chapter 2.7.3 --- Complexity Analysis --- p.40 / Chapter 2.8 --- A Constructive Algorithm for the Optimization Problem --- p.43 / Chapter 2.9 --- A Modified Constructive Algorithm --- p.46 / Chapter 2.9.1 --- Algorithm --- p.46 / Chapter 2.9.2 --- Worst-Case Analysis --- p.50 / Chapter 2.9.3 --- Sufficient Condition for Efficient Algorithm H --- p.58 / Chapter 2.9.4 --- Average-Case Analysis --- p.62 / Chapter 2.10 --- Performance Evaluation --- p.65 / Chapter 2.10.1 --- Optimal Schedule --- p.65 / Chapter 2.10.2 --- Space Complexity Analysis --- p.67 / Chapter 2.10.3 --- Time Complexity Analysis --- p.68 / Chapter 2.10.4 --- Simulation of Algorithm F and Algorithm H --- p.70 / Chapter 2.11 --- Conclusion --- p.74 / Chapter 3 --- Vehicle Scheduling Problems with Time Window Constraints --- p.77 / Chapter 3.1 --- Introduction --- p.77 / Chapter 3.2 --- Problem Formulation and Notations --- p.79 / Chapter 3.3 --- NP-hardness of VSP-WINDOW-SLP --- p.83 / Chapter 3.3.1 --- A Transformation from PARTITION --- p.83 / Chapter 3.3.2 --- Intuitive Idea of the Reduction --- p.85 / Chapter 3.3.3 --- NP-completeness Proof --- p.87 / Chapter 3.4 --- Polynomial Time Algorithm for the VSP-WINDOW on a Straight Line with Common Ready Time --- p.98 / Chapter 3.5 --- Strong NP-hardness of VSP-WINDOW-TREEP --- p.106 / Chapter 3.5.1 --- A Transformation from 3-PARTITION --- p.107 / Chapter 3.5.2 --- NP-completeness Proof --- p.107 / Chapter 3.6 --- Conclusion --- p.111 / Chapter 4 --- Conclusion --- p.115 / Bibliography --- p.119

Wong, Wing Chun. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2008. / Includes bibliographical references (leaves 66-67). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgement --- p.iii / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Background Study --- p.4 / Chapter 2.1 --- Basic Definitions and Notations --- p.5 / Chapter 2.2 --- Tarjan and Trojanowski's algorithm --- p.6 / Chapter 2.2.1 --- Techniques --- p.6 / Chapter 2.2.2 --- Algorithm --- p.8 / Chapter 2.3 --- "Fomin, Grandoni and Kratsch's Algorithm" --- p.9 / Chapter 2.3.1 --- Techniques --- p.9 / Chapter 2.3.2 --- Algorithm --- p.14 / Chapter 3 --- Improvements --- p.18 / Chapter 3.1 --- Tarjan and Trojanowski´ةs Algorithm --- p.18 / Chapter 3.1.1 --- Correctness and Running Time Analysis --- p.28 / Chapter 3.1.2 --- Improvement --- p.30 / Chapter 3.1.3 --- Using more weights --- p.35 / Chapter 3.2 --- The First Algorithm --- p.37 / Chapter 3.2.1 --- Standard Analysis --- p.37 / Chapter 3.2.2 --- Measure and Conquer --- p.38 / Chapter 3.2.3 --- Using more weights --- p.42 / Chapter 3.3 --- The Second Algorithm --- p.43 / Chapter 3.3.1 --- Running Time Analysis --- p.44 / Chapter 3.3.2 --- Using More Weights --- p.45 / Chapter 3.4 --- The Third Algorithm --- p.46 / Chapter 4 --- Lower Bounds --- p.52 / Chapter 4.1 --- Tarjan and Trojanowski's Algorithm --- p.52 / Chapter 4.2 --- The First Algorithm --- p.55 / Chapter 4.3 --- The Second Algorithm --- p.58 / Chapter 4.4 --- The Third Algorithm --- p.60 / Chapter 5 --- Conclusion --- p.63 / Bibliography --- p.66

Not available / text

Thesis (Ph. D.)--University of Washington, 1991. / Vita. Includes bibliographical references (leaves [160]-168).

Random NP-Complete problems have come under study as an important tool used in the analysis of optimization algorithms and help in our understanding of how to properly address issues of computational intractability. In this thesis, the Number Partition Problem and the Hamiltonian Cycle Problem are taken as representative NP-Complete classes. Numerical evidence is presented for a phase transition in the probability of solution when a modified Lévy-Stable distribution is used in instance creation for each. Numerical evidence is presented that show hard random instances exist near the critical threshold for the Hamiltonian Cycle problem. A choice of order parameter for the Number Partition Problem’s phase transition is also given. Finding Hamiltonian Cycles in Erdös-Rényi random graphs is well known to have almost sure polynomial time algorithms, even near the critical threshold. To the author’s knowledge, the graph ensemble presented is the first candidate, without specific graph structure built in, to generate graphs whose Hamiltonicity is intrinsically hard to determine. Random graphs are chosen via their degree sequence generated from a discretized form of Lévy-Stable distributions. Graphs chosen from this distribution still show a phase transition and appear to have a pickup in search cost for the algorithms considered. Search cost is highly dependent on the particular algorithm used and the graph ensemble is presented only as a potential graph ensemble to generate intrinsically hard graphs that are difficult to test for Hamiltonicity. Number Partition Problem instances are created by choosing each element in the list from a modified Lévy-Stable distribution. The Number Partition Problem has no known good approximation algorithms and so only numerical evidence to show the phase transition is provided without considerable focus on pickup in search cost for the solvers used. The failure of current approximation algorithms and potential candidate approximation algorithms are discussed.

Kwok-Shing Ho. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2002. / Includes bibliographical references (leaves 69-71). / Abstracts in English and Chinese. / List of Figures --- p.vi / List of Tables --- p.vii / Chapter Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Overview --- p.1 / Chapter 1.2 --- Thesis Objectives --- p.6 / Chapter 1.3 --- Outline of Thesis --- p.8 / Chapter Chapter 2 --- The Spare Capacity Planning Problem --- p.9 / Chapter 2.1 --- Mathematical Model of the Spare Capacity Planning Problem --- p.12 / Chapter 2.1.1 --- Variable Definitions --- p.12 / Chapter 2.1.2 --- Objective Function and Constraints --- p.15 / Chapter 2.1.3 --- Complexity --- p.17 / Chapter 2.2 --- Greedy Algorithm - Spare Capacity Allocation and Planning Estimator (SCAPE) --- p.19 / Chapter 2.2.1 --- Working Principle of SCAPE --- p.20 / Chapter 2.2.2 --- Implementation of SCAPE --- p.22 / Chapter 2.2.3 --- Improved SCAPE --- p.23 / Chapter 2.3 --- Experimental Results and Discussion --- p.27 / Chapter 2.3.1 --- Experimental Platform --- p.27 / Chapter 2.3.2 --- Experiment about Accuracy of SCAPE --- p.27 / Chapter 2.3.3 --- Experiment about Minimization of Network Spare Capacity --- p.30 / Chapter 2.3.4 --- Experiment about Minimization of Network Spare Cost --- p.35 / Chapter 2.4 --- Conclusions --- p.38 / Chapter Chapter 3 --- Survivable All-Optical Network Design Problem --- p.39 / Chapter 3.1 --- Mathematical Model of the Survivable Network Design Problem --- p.42 / Chapter 3.2 --- Optimization Algorithms for Survivable Network Design Problem --- p.44 / Chapter 3.2.1 --- Modified Drop Algorithm (MDA) --- p.45 / Chapter 3.2.1.1 --- Drop Algorithm Introduction --- p.45 / Chapter 3.2.1.2 --- Network Design with MDA --- p.45 / Chapter 3.2.2 --- Genetic Algorithm --- p.47 / Chapter 3.2.2.1 --- Genetic Algorithm Introduction --- p.47 / Chapter 3.2.2.2 --- Network Design with GA --- p.48 / Chapter 3.2.3 --- Complexity of MDA and GA --- p.51 / Chapter 3.3 --- Experimental Results and Discussion --- p.52 / Chapter 3.3.1 --- Experimental Platform --- p.52 / Chapter 3.3.2 --- Experiment about Accuracy of MDA and GA --- p.52 / Chapter 3.3.3 --- Experiment about Principle of Survivable Network Design --- p.55 / Chapter 3.3.4 --- Experiment about Performance of MDA and GA --- p.58 / Chapter 3.4 --- Conclusions --- p.62 / Chapter Chapter 4 --- Conclusions and Future Work --- p.63 / Appendix A The Interference Heuristic for the path restoration scheme --- p.66 / Bibliography --- p.69 / Publications --- p.72

by Lui Oi Lun Irene. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2001. / Includes bibliographical references (leaves 128-132). / Abstracts in English and Chinese. / List of Figures --- p.vii / List of Tables --- p.viii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Satisfiability Problem --- p.1 / Chapter 1.2 --- Motivation of the Research --- p.1 / Chapter 1.3 --- Overview of the Thesis --- p.2 / Chapter 2 --- Constraint Satisfaction Problem and Satisfiability Problem --- p.4 / Chapter 2.1 --- Constraint Programming --- p.4 / Chapter 2.2 --- Satisfiability Problem --- p.6 / Chapter 2.3 --- Methods in Solving SAT problem --- p.7 / Chapter 2.3.1 --- Davis-Putnam-Loveland Procedure --- p.7 / Chapter 2.3.2 --- SATZ by Chu-Min Li --- p.8 / Chapter 2.3.3 --- Local Search for SAT --- p.11 / Chapter 2.3.4 --- Integer Linear Programming Method for SAT --- p.12 / Chapter 2.3.5 --- Semidefinite Programming Method --- p.13 / Chapter 2.4 --- Softwares for SAT --- p.15 / Chapter 2.4.1 --- SAT01 --- p.15 / Chapter 2.4.2 --- "SATZ and SATZ213, contributed by Chu-Min Li" --- p.15 / Chapter 2.4.3 --- Others --- p.15 / Chapter 3 --- Integer Programming --- p.17 / Chapter 3.1 --- Introduction --- p.17 / Chapter 3.1.1 --- Formulation of IPs and BIPs --- p.18 / Chapter 3.1.2 --- Binary Search Tree --- p.19 / Chapter 3.2 --- Methods in Solving IP problem --- p.19 / Chapter 3.2.1 --- Branch-and-Bound Method --- p.20 / Chapter 3.2.2 --- Cutting-Plane Method --- p.23 / Chapter 3.2.3 --- Duality in Integer Programming --- p.26 / Chapter 3.2.4 --- Heuristic Algorithm --- p.28 / Chapter 3.3 --- Zero-one Optimization and Continuous Relaxation --- p.29 / Chapter 3.3.1 --- Introduction --- p.29 / Chapter 3.3.2 --- The Roof Dual expressed in terms of Lagrangian Relaxation --- p.30 / Chapter 3.3.3 --- Determining the Existence of a Duality Gap --- p.31 / Chapter 3.4 --- Software for solving Integer Programs --- p.33 / Chapter 4 --- Integer Programming Formulation for SAT Problem --- p.35 / Chapter 4.1 --- From 3-CNF SAT Clauses to Zero-One IP Constraints --- p.35 / Chapter 4.2 --- From m-Constrained IP Problem to Singly-Constrained IP Problem --- p.38 / Chapter 4.2.1 --- Example --- p.39 / Chapter 5 --- A Basic Branch-and-Bound Algorithm for the Zero-One Polynomial Maximization Problem --- p.42 / Chapter 5.1 --- Reason for choosing Branch-and-Bound Method --- p.42 / Chapter 5.2 --- Searching Algorithm --- p.43 / Chapter 5.2.1 --- Branch Rule --- p.44 / Chapter 5.2.2 --- Bounding Rule --- p.46 / Chapter 5.2.3 --- Fathoming Test --- p.46 / Chapter 5.2.4 --- Example --- p.47 / Chapter 6 --- Revised Bound Rule for Branch-and-Bound Algorithm --- p.55 / Chapter 6.1 --- Revised Bound Rule --- p.55 / Chapter 6.1.1 --- CPLEX --- p.57 / Chapter 6.2 --- Example --- p.57 / Chapter 6.3 --- Conclusion --- p.65 / Chapter 7 --- Revised Branch Rule for Branch-and-Bound Algorithm --- p.67 / Chapter 7.1 --- Revised Branch Rule --- p.67 / Chapter 7.2 --- Comparison between Branch Rule and Revised Branch Rule --- p.69 / Chapter 7.3 --- Example --- p.72 / Chapter 7.4 --- Conclusion --- p.73 / Chapter 8 --- Experimental Results and Analysis --- p.80 / Chapter 8.1 --- Experimental Results --- p.80 / Chapter 8.2 --- Statistical Analysis --- p.33 / Chapter 8.2.1 --- Analysis of Search Techniques --- p.83 / Chapter 8.2.2 --- Discussion of the Performance of SATZ --- p.85 / Chapter 9 --- Concluding Remarks --- p.87 / Chapter 9.1 --- Conclusion --- p.87 / Chapter 9.2 --- Suggestions for Future Research --- p.88 / Chapter A --- Searching Procedures for Solving Constraint Satisfaction Problem (CSP) --- p.91 / Chapter A.1 --- Notation --- p.91 / Chapter A.2 --- Procedures for Solving CSP --- p.92 / Chapter A.2.1 --- Generate and Test --- p.92 / Chapter A.2.2 --- Standard Backtracking --- p.93 / Chapter A.2.3 --- Forward Checking --- p.94 / Chapter A.2.4 --- Looking Ahead --- p.95 / Chapter B --- Complete Results for Experiments --- p.96 / Chapter B.1 --- Complete Result for SATZ --- p.96 / Chapter B.1.1 --- n =5 --- p.95 / Chapter B.1.2 --- n = 10 --- p.98 / Chapter B.1.3 --- n = 30 --- p.99 / Chapter B.2 --- Complete Result for Basic Branch-and-Bound Algorithm --- p.101 / Chapter B.2.1 --- n二5 --- p.101 / Chapter B.2.2 --- n = 10 --- p.104 / Chapter B.2.3 --- n = 30 --- p.107 / Chapter B.3 --- Complete Result for Revised Bound Rule --- p.109 / Chapter B.3.1 --- n = 5 --- p.109 / Chapter B.3.2 --- n = 10 --- p.112 / Chapter B.3.3 --- n = 30 --- p.115 / Chapter B.4 --- Complete Result for Revised Branch-and-Bound Algorithm --- p.118 / Chapter B.4.1 --- n = 5 --- p.118 / Chapter B.4.2 --- n = 10 --- p.121 / Chapter B.4.3 --- n = 30 --- p.124 / Bibliography --- p.128