The axial map of a town is one of the key components of the space syntax method – a tool for analysing urban layout. It is derived by placing the longest and fewest lines, called axial lines, to cross the adjacencies between convex polygons in a convex map of a town. Previous research has shown that placing axial lines to cross the adjacencies between a collection of convex polygons is NP-complete, even when the convex polygons are restricted to rectangles and the axial lines to have orthogonal orientation. In this document, we show that placing orthogonal axial lines in orthogonal rectangles where the adjacencies between the rectangles are restricted to be crossed only once (ALPSC- OLOR) is NP-complete. As a result, we infer the single adjacency crossing version of the general axial line placement problem is NP-complete. The transformation of NPcompleteness of ALP-SC-OLOR is from vertex cover for biconnected planar graphs. A heuristic is then presented that gives a reasonable approximate solution to ALP-SC-OLOR based on a greedy method.

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

Computational complexity theory usually investigates the complexity of sets, i.e., the complexity of partitions into two parts. But often it is more appropriate to represent natural problems by partitions into more than two parts. A particularly interesting class of such problems consists of classification problems for relations. For instance, a binary relation R typically defines a partitioning of the set of all pairs (x,y) into four parts, classifiable according to the cases where R(x,y) and R(y,x) hold, only R(x,y) or only R(y,x) holds or even neither R(x,y) nor R(y,x) is true. By means of concrete classification problems such as Graph Embedding or Entailment (for propositional logic), this thesis systematically develops tools, in shape of the boolean hierarchy of NP-partitions and its refinements, for the qualitative analysis of the complexity of partitions generated by NP-relations. The Boolean hierarchy of NP-partitions is introduced as a generalization of the well-known and well-studied Boolean hierarchy (of sets) over NP. Whereas the latter hierarchy has a very simple structure, the situation is much more complicated for the case of partitions into at least three parts. To get an idea of this hierarchy, alternative descriptions of the partition classes are given in terms of finite, labeled lattices. Based on these characterizations the Embedding Conjecture is established providing the complete information on the structure of the hierarchy. This conjecture is supported by several results. A natural extension of the Boolean hierarchy of NP-partitions emerges from the lattice-characterization of its classes by considering partition classes generated by finite, labeled posets. It turns out that all significant ideas translate from the case of lattices. The induced refined Boolean hierarchy of NP-partitions enables us more accuratly capturing the complexity of certain relations (such as Graph Embedding) and a description of projectively closed partition classes. / Die klassische Komplexitätstheorie untersucht in erster Linie die Komplexität von Mengen, d.h. von Zerlegungen (Partitionen) einer Grundmenge in zwei Teile. Häufig werden aber natürliche Fragestellungen viel angemessener durch Zerlegungen in mehr als zwei Teile abgebildet. Eine besonders interessante Klasse solcher Fragestellungen sind Klassifikationsprobleme für Relationen. Zum Beispiel definiert eine Binärrelation R typischerweise eine Zerlegung der Menge aller Paare (x,y) in vier Teile, klassifizierbar danach, ob R(x,y) und R(y,x), R(x,y) aber nicht R(y,x), nicht R(x,y) aber dafür R(y,x) oder weder R(x,y) noch R(y,x) gilt. Anhand konkreter Klassifikationsprobleme, wie zum Beispiel der Einbettbarkeit von Graphen und der Folgerbarkeit für aussagenlogische Formeln, werden in der Dissertation Instrumente für eine qualitative Analyse der Komplexität von Partitionen, die von NP-Relationen erzeugt werden, in Form der Booleschen Hierarchie der NP-Partitionen und ihrer Erweiterungen systematisch entwickelt. Die Boolesche Hierarchie der NP-Partitionen wird als Verallgemeinerung der bereits bekannten und wohluntersuchten Boolesche Hierarchie über NP eingeführt. Während die letztere Hierarchie eine sehr einfache Struktur aufweist, stellt sich die Boolesche Hierarchie der NP-Partitionen im Falle von Zerlegungen in mindestens 3 Teile als sehr viel komplizierter heraus. Um einen Überblick über diese Hierarchien zu erlangen, werden alternative Beschreibungen der Klassen der Hierarchien mittels endlicher, bewerteter Verbände angegeben. Darauf aufbauend wird die Einbettungsvermutung aufgestellt, die uns die vollständige Information über die Struktur der Hierarchie liefert. Diese Vermutung wird mit verschiedene Resultaten untermauert. Eine Erweiterung der Booleschen Hierarchie der NP-Partitionen ergibt sich auf natürliche Weise aus der Charakterisierung ihrer Klassen durch Verbände. Dazu werden Klassen betrachtet, die von endlichen, bewerteten Halbordnungen erzeugt werden. Es zeigt sich, dass die wesentlichen Konzepte vom Verbandsfall übertragen werden können. Die entstehende Verfeinerung der Booleschen Hierarchie der NP-Partitionen ermöglicht die exaktere Analyse der Komplexität bestimmter Relationen (wie zum Beispiel der Einbettbarkeit von Graphen) und die Beschreibung projektiv abgeschlossener Partitionenklassen.

A cross-sectional study of the performance of groups of Vietnamese learners is reported with focus on how they deal with the expression of number in English (singular/plural; definite/indefinite) through a cloze exercise and a translation excercise. This research investigates the hypothesis that some NP environments facilitate the distinction between singular and plural, count and mass, and that the context in which a noun is used can provide positive clues to the choice of number in nouns. It has been found that transfer of Vietnamese NP structures into English occurred where the NP environment was not obviously countable or uncountable, i.e., it has no conspicuous structural signals for number determination. Transfer was also found where an NP was taken from its context. The analysis of learners' errors gives some insight into ways in which the teaching of the number expression can be made more effective and beneficial for Vietnamese learners. A number of activities were suggested, which enable the teacher to exploit the advantages of NP environments to convey the syntactic-semantic properties of number to learners. Communicative practice of NP structures (e.g., in a conversation or a role play activity) can make learners aware of different aspects of the number expression in English. It is argued that the pragmatic aspect of the number expression is most important as in use, the syntactic and semantic properties of the category of number are unified to achieve communicative purposes.

<p>In the maximum solution equation problem a collection of equations are given over some algebraic structure. The objective is to find an assignment to the variables in the equations such that all equations are satisfied and the sum of the variables is maximised. We give tight approximability results for the maximum solution equation problem when the equations are given over finite abelian groups. We also prove that the weighted and unweighted versions of this problem have asymptotically equal approximability thresholds.</p><p>Furthermore, we show that the problem is equally hard to solve as the general problem even if each equation is restricted to contain at most three variables and solvable in polynomial time if the equations are restricted to contain at most two variables each. All of our results also hold for the generalised version of maximum solution equation where the elements of the group are mapped arbitrarily to non-negative integers in the objective function.</p>

<p>This thesis presents exact means to solve a family of NP-hard problems. Starting with the well-studied Exact Satisfiability problem (XSAT) parents, siblings and daughters are derived and studied, each with interesting practical and theoretical properties. While developing exact algorithms to solve the problems, we gain new insights into their structure and mutual similarities and differences.</p><p>Given a Boolean formula in CNF, the XSAT problem asks for an assignment to the variables such that each clause contains exactly one true literal. For this problem we present an <em>O</em>(1.1730ⁿ) time algorithm, where n is the number of variables. XSAT is a special case of the General Exact Satisfiability problem which asks for an assignment such that in each clause exactly i literals be true. For this problem we present an algorithm which runs in <em>O</em>(2^(1-<em>ε</em>⁾<em>n</em>) time, with 0 < <em>ε</em> < 1 for every fixed <em>i</em>; for <em>i</em>=2, 3 and 4 we have running times in <em>O</em>(1.4511ⁿ), <em>O</em>(1.6214ⁿ) and <em>O</em>(1.6848ⁿ) respectively.</p><p>For the counting problems we present an O(1.2190ⁿ) time algorithm which counts the number of models for an XSAT instance. We also present algorithms for #2SAT<em>w</em><em> </em>and #3SAT<em>w</em><em>,</em> two well studied Boolean problems. The algorithms have running times in O(1.2561ⁿ) and <em>O</em>(1.6737ⁿ) respectively.</p><p>Finally we study optimisation problems: As a variant of the Maximum Exact Satisfiability problem, consider the problem of finding an assignment exactly satisfying a maximum number of clauses while the rest are left with no true literal. This problem is reducible to #2SAT<em>w</em> without the addition of new variables and thus is solvable in time <em>O</em>(1.2561ⁿ). Another interesting optimisation problem is to find two XSAT models which differ in as many variables as possible. This problem is shown to be solvable in O(1.8348ⁿ) time.</p>

There are four phenomena that are particularly troublesome for theories of ellipsis: <br>the existence of sloppy readings when the relevant pronouns cannot possibly be bound; an ellipsis being resolved in such a way that an ellipsis site in the antecedent is not understood in the way it was there; an ellipsis site drawing material from two or more separate antecedents; and ellipsis with no linguistic antecedent. <br>These cases are accounted for by means of a new theory that involves copying syntactically incomplete antecedent material and an analysis of silent VPs and NPs that makes them into higher order definite descriptions that can be bound into.

This thesis presents exact means to solve a family of NP-hard problems. Starting with the well-studied Exact Satisfiability problem (XSAT) parents, siblings and daughters are derived and studied, each with interesting practical and theoretical properties. While developing exact algorithms to solve the problems, we gain new insights into their structure and mutual similarities and differences. Given a Boolean formula in CNF, the XSAT problem asks for an assignment to the variables such that each clause contains exactly one true literal. For this problem we present an O(1.1730n) time algorithm, where n is the number of variables. XSAT is a special case of the General Exact Satisfiability problem which asks for an assignment such that in each clause exactly i literals be true. For this problem we present an algorithm which runs in O(2(1-ε) n) time, with 0 &lt; ε &lt; 1 for every fixed i; for i=2, 3 and 4 we have running times in O(1.4511n), O(1.6214n) and O(1.6848n) respectively. For the counting problems we present an O(1.2190n) time algorithm which counts the number of models for an XSAT instance. We also present algorithms for #2SATw and #3SATw, two well studied Boolean problems. The algorithms have running times in O(1.2561n) and O(1.6737n) respectively. Finally we study optimisation problems: As a variant of the Maximum Exact Satisfiability problem, consider the problem of finding an assignment exactly satisfying a maximum number of clauses while the rest are left with no true literal. This problem is reducible to #2SATw without the addition of new variables and thus is solvable in time O(1.2561n). Another interesting optimisation problem is to find two XSAT models which differ in as many variables as possible. This problem is shown to be solvable in O(1.8348n) time.

Geometric covering problems have always been of focus in computer scientific research. The generic geometric covering problem asks to cover a set S of n objects with another set of objects whose cardinality is minimum, in a geometric setting. Many versions of geometric cover have been studied in detail, one of which is line cover: Given a set of points in the plane, find the minimum number of lines to cover them. In Euclidean space Rm, this problem is known as Hyperplane Cover, where lines are replaced by affine hyperplanes bounded by dimension d. Line cover is NP-hard, so is its hyperplane analogue. Our thesis focuses on few extensions of hyperplane cover and line cover. One of the techniques used to study NP-hard problems is Fixed Parameter Tractability (FPT), where, in addition to input size, a parameter k is provided for input instance. We ask to solve the problem with respect to k, such that the running time is a function in both n and k, strictly polynomial in n, while the exponential component is limited to k. In this thesis, we study FPT and parameterized complexity theory, the theory of classifying hard problems involving a parameter k. We focus on two new geometric covering problems: covering a set of points in the plane with conics (conic cover) and covering a set of points with strips or fat lines of given width in the plane (fat line cover). A conic is a non-degenerate curve of degree two in the plane. A fat line is defined as a strip of finite width w. In this dissertation, we focus on the parameterized versions of these two problems, where, we are asked to cover the set of points with k conics or k fat lines. We use the existing techniques of FPT algorithms, kernelization and approximation algorithms to study these problems. We do a comprehensive study of these problems, starting with NP-hardness results to studying their parameterized hardness in terms of parameter k. We show that conic cover is fixed parameter tractable, and give an algorithm of running time O∗ ((k/1.38)^4k), where, O∗ implies that the running time is some polynomial in input size. Utilizing special properties of a parabola, we are able to achieve a faster algorithm and show a running time of O∗ ((k/1.15)^3k). For fat line cover, first we establish its NP-hardness, then we explore algorithmic possibilities with respect to parameterized complexity theory. We show W [1]-hardness of fat line cover with respect to the number of fat lines, by showing a parameterized reduction from the problem of stabbing axis-parallel squares in the plane. A parameterized reduction is an algorithm which transforms an instance of one parameterized problem into an instance of another parameterized problem using a FPT-algorithm. In addition, we show that some restricted versions of fat line cover are also W [1]-hard. Further, in this thesis, we explore a restricted version of fat line cover, where the set of points are integer coordinates and allow only axis-parallel lines to cover them. We show that the problem is still NP-hard. We also show that this version is fixed parameter tractable having a kernel size of O (k^2) and give a FPT-algorithm with a running time of O∗ (3^k). Finally, we conclude our study on this problem by giving an approximation algorithm for this version having a constant approximation ratio 2.