No description available.

No description available.

No description available.

Thesis (M.S.)--University of Wisconsin--Madison, 1967. / eContent provider-neutral record in process. Description based on print version record. Includes bibliographical references.

Thesis (M.S.)--University of Missouri, School of Mines and Metallurgy, 1949. / Vita. The entire thesis text is included in file. Typescript. Title from title screen of thesis/dissertation PDF file (viewed June 30, 2010) Includes bibliographical references (p. 40).

Covering relaxation algorithms were first developed by Granot et al for solving positive 0-1 polynomial programming (PP) problems which maximize a linear objective function in 0-1 variables subject to a set of polynomial inequalities containing only positive coefficients ["Covering Relaxation for Positive 0-1 Polynomial Programs", Management Science, Vol. 25, (1979)]. The covering relaxation approach appears to cope successfully with the non-linearity of the PP problem and is able to solve modest size (40 variables and 40 constraints) sparse PP problems. This thesis develops a more sophisticated covering relaxation method which accelerates the performance of this approach, especially when solving PP problems with many terms in a constraint. Both the original covering relaxation algorithm and the newly introduced accelerated algorithm are cutting plane algorithms in which the relaxed problem is the set covering problem and the cutting planes are linear covering constraints. In contrast with other cutting plane methods in integer programming, the accelerated covering relaxation algorithm developed in this thesis does not solve the relaxed problem to optimality after the introduction of the cutting plane constraints. Rather, the augmented relaxed problem is first solved approximately and only if the approximate solution is feasible to the PP problem is the relaxed problem solved to optimality. The promise of this approach stems from the excellent performance of approximate procedures for solving integer programming problems. Indeed, the extensive computational experiments that were performed show that the accelerated algorithm has reduced both the number of set covering problems to be solved and the overall time required to solve a PP problem. The improvements are particularly significant for PP problems with many terms in a constraint. / Science, Faculty of / Computer Science, Department of / Graduate

No description available.

Woo Hok Luen. / Thesis (M.Sc.)--Chinese University of Hong Kong, 1992. / Includes bibliographical references (leaves 42-43). / Abstract --- p.2 / Chapter Ch. 1 --- Introduction --- p.3 / Chapter Ch. 2 --- Review --- p.4 / Chapter 2.1 --- Definitions and notions --- p.4 / Chapter 2.2 --- Features of a skeleton --- p.5 / Chapter 2.3 --- Parallel and sequential algorithms --- p.6 / Chapter 2.4 --- Distance transformations --- p.7 / Chapter 2.5 --- Relaxation labelling process --- p.8 / Chapter Ch. 3 --- The proposed algorithm --- p.9 / Chapter 3.1 --- Definitions and notions --- p.9 / Chapter 3.2 --- The thinning problem --- p.13 / Chapter 3.3 --- Assigning initial probabilities --- p.14 / Chapter 3.4 --- Iteration schemes --- p.15 / Chapter 3.5 --- Net increment of the skeletal probabilities --- p.16 / Chapter 3.6 --- Net increment of the nonskeletal probabilities --- p.16 / Chapter 3.7 --- Terminating condition --- p.19 / Chapter Ch. 4 --- Experimental results --- p.21 / Chapter 4.1 --- Parameters --- p.21 / Chapter 4.2 --- Results --- p.23 / Chapter Ch. 5 --- Discussion --- p.29 / Chapter 5.1 --- 4-neighbour and 8-neighbour DT --- p.30 / Chapter 5.2 --- 8-connectivity number and safe-point tests --- p.32 / Chapter 5.3 --- Mutual exclusion problem --- p.33 / Chapter 5.4 --- Skeleton not of unit width --- p.34 / Chapter 5.5 --- Development --- p.35 / Chapter Ch. 6 --- Conclusion --- p.35 / Appendix --- p.36 / Reference --- p.42

Chan, Yuk Hei. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (leaves 49-51). / Abstract also in Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Problem Definition --- p.1 / Chapter 1.1.1 --- Hypergraph Matching --- p.1 / Chapter 1.1.2 --- k-Set Packing --- p.2 / Chapter 1.1.3 --- k-Dimensional Matching --- p.2 / Chapter 1.1.4 --- Related Problems --- p.2 / Chapter 1.2 --- Main Result --- p.5 / Chapter 1.3 --- Overview of the Thesis --- p.6 / Chapter 2 --- Background --- p.8 / Chapter 2.1 --- Matching --- p.8 / Chapter 2.1.1 --- Augmenting Path --- p.8 / Chapter 2.1.2 --- Linear Programming --- p.10 / Chapter 2.1.3 --- Matching in General Graphs --- p.11 / Chapter 2.1.4 --- Approximate Min-max Relation for Hypergraphs --- p.11 / Chapter 2.2 --- Local Search --- p.12 / Chapter 2.2.1 --- Unweighted k-Set Packing --- p.12 / Chapter 2.2.2 --- Weighted k-Set Packing ´ؤ (k- - 1 + ₂ё)-approximation --- p.14 / Chapter 2.2.3 --- Weighted k-Set Packing´ؤ(2(k + l)/3 + ₂ё)-approximation --- p.15 / Chapter 2.2.4 --- Weighted k-Set Packing´ؤ((k + l)/2 + ₂ё)-approximation --- p.16 / Chapter 2.3 --- Iterative Rounding --- p.17 / Chapter 2.3.1 --- Basic Solution --- p.17 / Chapter 2.3.2 --- Bipartite Matching --- p.19 / Chapter 2.3.3 --- Generalized Steiner Network Problem --- p.20 / Chapter 2.3.4 --- Minimum Bounded Degree Spanning Tree --- p.22 / Chapter 2.4 --- Packing Problems --- p.24 / Chapter 2.4.1 --- Projective Plane --- p.26 / Chapter 2.5 --- Local Ratio --- p.28 / Chapter 2.5.1 --- Vertex Cover --- p.28 / Chapter 2.5.2 --- Local Ratio Theorem --- p.29 / Chapter 2.5.3 --- Feedback Vertex Set in Tournaments --- p.29 / Chapter 2.5.4 --- Fractional Local Ratio --- p.31 / Chapter 2.5.5 --- Maximum Weight Independent Set in t-interval Graph --- p.31 / Chapter 3 --- k-Dimensional Matching --- p.33 / Chapter 3.1 --- Integrality Gap of the Standard LP Relaxation --- p.33 / Chapter 3.1.1 --- Approximation Algorithm for Unweighted k-D Matching --- p.34 / Chapter 3.1.2 --- Fractional Colouring --- p.35 / Chapter 3.1.3 --- Produce an Ordering --- p.37 / Chapter 3.2 --- Approximation Algorithm for Weighted k-D Matching --- p.38 / Chapter 4 --- k-Set Packing --- p.40 / Chapter 4.1 --- Integrality Gap of the Standard LP Relaxation --- p.40 / Chapter 4.2 --- Improved LP Relaxation for 3-SP --- p.41 / Concluding Remarks --- p.48 / Bibliography --- p.49

Thesis (Ph.D)--Industrial and Systems Engineering, Georgia Institute of Technology, 2010. / Committee Chair: Erera, Martin; Committee Chair: Nemhauser, George; Committee Chair: Savelsbergh, Martin; Committee Member: Ergun, Ozlem; Committee Member: Ferguson, Mark. Part of the SMARTech Electronic Thesis and Dissertation Collection.