This thesis is about the computational complexity of several classes of combinatorial optimization problems, all related to the constraint satisfaction problems. A constraint language consists of a domain and a set of relations on the domain. For each such language there is a constraint satisfaction problem (CSP). In this problem we are given a set of variables and a collection of constraints, each of which is constraining some variables with a relation in the language. The goal is to determine if domain values can be assigned to the variables in a way that satisfies all constraints. An important question is for which constraint languages the corresponding CSP can be solved in polynomial time. We study this kind of question for optimization problems related to the CSPs. The main focus is on extended minimum cost homomorphism problems. These are optimization versions of CSPs where instances come with an objective function given by a weighted sum of unary cost functions, and where the goal is not only to determine if a solution exists, but to find one of minimum cost. We prove a complete classification of the complexity for these problems on three-element domains. We also obtain a classification for the so-called conservative case. Another class of combinatorial optimization problems are the surjective maximum CSPs. These problems are variants of CSPs where a non-negative weight is attached to each constraint, and the objective is to find a surjective mapping of the variables to values that maximizes the weighted sum of satisfied constraints. The surjectivity requirement causes these problems to behave quite different from for example the minimum cost homomorphism problems, and many powerful techniques are not applicable. We prove a dichotomy for the complexity of the problems in this class on two-element domains. An essential ingredient in the proof is an algorithm that solves a generalized version of the minimum cut problem. This algorithm might be of independent interest. In a final part we study properties of NP-hard optimization problems. This is done with the aid of restricted forms of polynomial-time reductions that for example preserves solvability in sub-exponential time. Two classes of optimization problems similar to those discussed above are considered, and for both we obtain what may be called an easiest NP-hard problem. We also establish some connections to the exponential time hypothesis.

The price of anarchy, a concept introduced by Koutsoupias and Papadimitriou [9], is the main topic of this thesis. It is a measure of the loss of efficiency that occurs when there is no central control over a system consisting of many "selfish" agents. We will be particularly interested in this in the context of network games, which can be used to model congestion in traffic and communication networks. / After an introduction of the relevant concepts and review of related work, we proceed with the new results of this thesis. We provide a new upper bound for the price of anarchy in the case of atomic unsplittable agents with polynomial cost functions, and demonstrate that it is tight by an explicit construction. We then introduce a new model for network routing that introduces priorities; users with a higher priority on a link will be able to traverse the link more quickly. Our model is fairly general, and allows various different priority schemes for modelling different situations. One particularly interesting version, which we have dubbed the timestamp game, assigns priorities according to the order of arrival at the start of the link. / We derive tight upper bounds for the price of anarchy in our model in the case of polynomial cost functions and nonatomic agents. We also obtain tight results in the unsplittable case with linear cost functions, and an upper bound with polynomial cost functions. / While we concentrate on network games, most of the results carry through to the more general class of congestion games, which we also discuss.

Thesis (Ph. D.)--University of North Texas, Aug., 2007. / Title from title page display. Includes bibliographical references.

Univ., Habil.-Schr--Zürich. / Literaturverz. S. [149] - 157.

Thesis (Ph. D.)--University of Washington, 1998. / Vita. Includes bibliographical references (p. [155]-167).

Thesis (M.S.) -- Worcester Polytechnic Institute. / Keywords: private-key cryptography; Advanced Encryption Standard; K-secure; hermetic; block cipher; circuit complexity. Includes bibliographical references (p. 75-79).

Thesis (M.S.)--Brigham Young University. Dept. of Mathematics, 2005. / Includes bibliographical references (p. 39-40).

Thesis (M.S.)--Duquesne University, 2005. / Title from document title page. Abstract included in electronic submission form. Includes bibliographical references (p. 21) and index.

Thesis (Ph. D.)--University of Texas at Austin, 2006. / Vita. Includes bibliographical references.

Thesis (Ph. D.)--University of Washington, 2000. / Vita. Includes bibliographical references (p. 142-150).