Knapsack problem has been widely studied in computer science for years. There exist several variants of the problem, with zero-one maximum knapsack in one dimension being the simplest one. In this thesis we study several existing approximation algorithms for the minimization version of the problem and propose a scaling based fully polynomial time approximation scheme for the minimum knapsack problem. We compare the performance of this algorithm with existing algorithms. Our experiments show that, the proposed algorithm runs fast and has a good performance ratio in practice. We also conduct extensive experiments on the data provided by Canadian Pacific Logistics Solutions during the MITACS internship program. We propose a scaling based e-approximation scheme for the multidimensional (d-dimensional) minimum knapsack problem and compare its performance with a generalization of a greedy algorithm for minimum knapsack in d dimensions. Our experiments show that the e- approximation scheme exhibits good performance ratio in practice. / x, 85 leaves ; 29 cm

L'étude que nous proposons s'inscrit dans le cadre de la complexité implicite des calculs. Selon Daniel Leivant, il s'agit de donner des caractérisations de la complexité sans faire de référence explicite à un modèle de calcul. Nous montrons que les interprétations de programmes sont un bon outil d'analyse dans ce contexte. Les aspects théoriques et pratiques sont abordés.

The Hypertext concept was introduced about 50 years ago. This thesis presents the development of a reference system using the Hypertext concept. HYATS (HYpertext Automata and Turing Theory Learning 5ys,em) is a system which helps users learn many topics in the area of theory of computation. The system is implemented by Guide which is a general purpose Hypertext system running on PC-Windows environment. HYATS also includes a Turing machine simulating program which was written by Dominique Atger as her Master's Thesis in 1993, so that users can actually experiment with Turing machines learned through HYATS. HYATS will be not only the reference system, but also the complete package of actual learning system. The motivation behind this project is to study basic concepts of a Hypertext system so that it will also contribute to G-Net research. HYATS can be used as a prototype for future development of versions of by using other Hypertext systems such as NoteCards. / Department of Computer Science

In this dissertation we examine several discrete optimization problems through the perspectives of modeling, complexity and algorithms. We first provide a probabilistic comparison of split and type 1 triangle cuts for mixed-integer programs with two rows and two integer variables in terms of cut coefficients and volume cutoff. Under a specific probabilistic model of the problem parameters, we show that for the above measure, the probability that a split cut is better than a type 1 triangle cut is higher than the probability that a type 1 triangle cut is better than a split cut. The analysis also suggests some guidelines on when type 1 triangle cuts are likely to be more effective than split cuts and vice versa. We next study a minimum concave cost network flow problem over a grid network. We give a polytime algorithm to solve this problem when the number of echelons is fixed. We show that the problem is NP-hard when the number of echelons is an input parameter. We also extend our result to grid networks with backward and upward arcs. Our result unifies the complexity results for several models in production planning and green recycling including the lot-sizing model, and gives the first polytime algorithm for some problems whose complexities were not known before. Finally, we examine how much complexity randomness will bring to a simple combinatorial optimization problem. We study a problem called the sell or hold problem (SHP). SHP is to sell k out of n indivisible assets over two stages, with known first-stage prices and random second-stage prices, to maximize the total expected revenue. Although the deterministic version of SHP is trivial to solve, we show that SHP is NP-hard when the second-stage prices are realized as a finite set of scenarios. We show that SHP is polynomially solvable when the number of scenarios in the second stage is constant. A max{1/2,k/n}-approximation algorithm is presented for the scenario-based SHP.

In this thesis we examine the computational complexity of certain digraph homomorphism problems. A homomorphism between digraphs, denoted by $f: G \to H$, is a mapping from the vertices of $G$ to the vertices of $H$ such that the arcs of $G$ are preserved. The problem of deciding whether a homomorphism to a fixed digraph $H$ exists is known as the $H$-colouring problem. We prove a generalization of a theorem due to Bang-Jensen, Hell and MacGillivray. Their theorem shows that for every semi-complete digraph $H$, $H$-colouring exhibits a dichotomy: $H$-colouring is either polynomial time solvable or it is NP-complete. We show that the class of local tournaments also exhibit a dichotomy. The NP-completeness results are found using direct NP-completeness reductions, indicator and vertex (and arc) sub-indicator constructions. The polynomial cases are handled by appealing to a result of Gutjhar, Woeginger and Welzl: the \underbar{$X$}-graft extension. We also provide a new proof of their result that follows directly from the consistency check. An unexpected result is the existence of unicyclic local tournaments with NP-complete homomorphism problems. During the last decade a new approach to studying the complexity of digraph homomorphism problems has emerged. This approach focuses attention on so-called polymorphisms as a measure of the complexity of a digraph homomorphism problem. For a digraph $H$, a polymorphism of arity $k$ is a homomorphism $f: H^k \to H$. Certain special polymorphisms are conjectured to be the key to understanding $H$-colouring problems. These polymorphisms are known as weak near unanimity functions (WNUFs). A WNUF of arity $k$ is a polymorphism $f: H^k \to H$ such that $f$ is idempotent an $f(y,x,x,\ldots,x)=f(x,y,x,\ldots,x)=f(x,x,y,\ldots,x) = \cdots = f(x,x,x,\ldots,y)$. We prove that a large class of polynomial time $H$-colouring problems all have a $\WNUF$. Furthermore we also prove some non-existence results for $\WNUF$s on certain digraphs. In proving these results, we develop a vertex (and arc) sub-indicator construction as well as an indicator construction in analogy with the ones developed by Hell and Ne{\v{s}}et{\v{r}}il. This is then used to show that all tournaments with at least two cycles do not admit a $\WNUF_k$ for $k>1$. This furnishes a new proof (in the case of tournaments) of the result by Bang-Jensen, Hell and MacGillivray referred to at the start. These results lend some support to the conjecture that $\WNUF$s are the ``right'' functions for measuring the complexity of $H$-colouring problems. We also study a related notion, namely that of an injective homomorphism. A homomorphism $f: G \to H$ is injective if the restriction of $f$ to the in-neighbours of every vertex in $G$ is an injective mapping. In order to classify the complexity of these problems we develop an indicator construction that is suited to injective homomorphism problems. For this type of digraph homomorphism problem we consider two cases: reflexive and irreflexive targets. In the case of reflexive targets we are able to classify all injective homomorphism problems as either belonging to the class of polynomial time solvable problems or as being NP-complete. Irreflexive targets pose more of a problem. The problem lies with targets of maximum in-degree equal to two. Targets with maximum in-degree one are polynomial, while targets with in-degree at least three are NP-complete. There is a transformation from (ordinary) graph homomorphism problems to injective, in-degree two, homomorphism problems (a reverse transformation also exists). This transformation provides some explanation as to the difficulty of the in-degree two case. We nonetheless classify all injective homomorphisms to irreflexive tournaments as either being a problem in P or a problem in the class of NP-complete problems. We also discuss some upper bounds on the injective oriented irreflexive (reflexive) chromatic number.

The present thesis is dedicated to two topics in Dynamics of Holomorphic maps. The first topic is dynamics of simple parabolic germs at the origin. The second topic is Polynomial-time Computability of Julia sets.\\ Dynamics of simple parabolic germs. Let $F$ be a germ with a simple parabolic fixed point at the origin: $F(w)=w+w^2+O(w^3).$ It is convenient to apply the change of coordinates $z=-1/w$ and consider the germ at infinity $$f(z)=-1/F(-1/z)=z+1+O(z^{-1}).$$ The dynamics of a germ $f$ can be described using Fatou coordinates. Fatou coordinates are analytic solutions of the equation $\phi(f(z))=\phi(z)+1.$ This equation has a formal solution \[\tilde\phi(z)=\text{const}+z+A\log z+\sum_{j=1}^\infty b_jz^{-j},\] where $\sum b_jz^{-j}$ is a divergent power series. Using \'Ecalle's Resurgence Theory we show that $\tilde$ can be interpreted as the asymptotic expansion of the Fatou coordinates at infinity. Moreover, the Fatou coordinates can be obtained from $\tilde \phi$ using Borel-Laplace summation. J.~\'Ecalle and S.~Voronin independently constructed a complete set of invariants of analytic conjugacy classes of germs with a parabolic fixed point. We give a new proof of validity of \'Ecalle's construction. \\ Computability of Julia sets. Informally, a compact subset of the complex plane is called \emph if it can be visualized on a computer screen with an arbitrarily high precision. One of the natural open questions of computational complexity of Julia sets is how large is the class of rational functions (in a sense of Lebesgue measure on the parameter space) whose Julia set can be computed in a polynomial time. The main result of Chapter II is the following: Theorem. Let $f$ be a rational function of degree $d\ge 2$. Assume that for each critical point $c\in J_f$ the $\omega$-limit set $\omega(c)$ does not contain either a critical point or a parabolic periodic point of $f$. Then the Julia set $J_f$ is computable in a polynomial time.

This thesis comprises of two separate game theoretic models that fall under the general umbrella of network formation games. The first is a coalitional model of interaction in social networks that is based on the idea of social distance, in which players seek interactions with similar others. Our model captures some of the phenomena observed on such networks, such as homophily driven interactions and the formation of small worlds for groups of players. Using social distance games, we analyze the interactions between players on the network, study the properties of efficient and stable networks, relate them to the underlying graphical structure of the game, and give an approximation algorithm for finding optimal social welfare. We then show that efficient networks are not necessarily stable, and stable networks do not necessarily maximise welfare. We use the stability gap to investigate the welfare of stable coalition structures, and propose two new solution concepts with improved welfare guarantees. The second model is a compact formulation of matchings with externalities. Our formulation achieves tractability of the representation at the expense of full expressivity. We formulate a template of solution concept that applies to games where externalities are involved, and instantiate it in the context of optimistic, neutral, and pessimistic reasoning. Then we investigate the complexity of the representation in the context of many-to-many and one-to-one matchings, and provide both computational hardness results and polynomial time algorithms where applicable.

Thesis (M.S.)--California Polytechnic State University, 2008. / Major professor: David Janzen, Ph.D. "Presented to the faculty of California Polytechnic State University, San Luis Obispo." "In partial fulfillment of the requirements for the degree [of] Master of Science in Computer Science." "June 2008." Includes bibliographical references (leaves 57-62). Also available online. Also available on microfiche (1 sheet).

Thesis (Ph. D.)--University of Washington, 2004. / Vita. Includes bibliographical references (p. 106-117).

Thesis (Ph. D.)--University of Texas at Austin, 2004. / Supervisors: James W. Fredrickson and Gautam Ahuja. Vita. Includes bibliographical references.