Algorithms for Problems in Voting and Scheduling

In this dissertation, we study the voting problem and the ranking problem in computational social choice, as well as a matching problem in a restricted graph. We present our results for these problems in two parts.Part I: Election, Ranking, and Heuristics. Voting is commonly used to reach consensus among a group of people. Voting models often deal with a set of voters, each of whom has a preference over a set of alternatives. Each voter submits a ranking of the alternatives, and the outcome is decided by a voting rule. Computational voting theory is an interdisciplinary research area which considers the computational problems that arise in voting. Selecting the winner(s) of an election is one such problem. The problem of computing the winner(s) using most voting rules is easy. However, there are a few rules for which this problem becomes computationally hard. In the first part of this thesis, we study two important voting and ranking rules under which computing the winner(s) is hard. The first voting procedure we study in this thesis is the Chamberlin-Courant system. The Chamberlin-Courant system is a proportional representation system that does not restrict candidates to have a minimum number of votes to be selected in an assembly. We consider domination analysis of a 2-Opt heuristic for the winner determination problem under the Chamberlin-Courant system. We show that the 2-Opt heuristic produces solutions no worse than the average solution in polynomial time. The next problem we consider in this dissertation is Linear Ordering Problem. Linear ordering problem is a classic optimization problem which can be used to model problems in graph theory, machine scheduling, and ranking. Relatively recently, there has been some success in using Mixed Integer Program (MIP) heuristic for NP-hard optimization problems. We report our experience with using a MIP heuristic for the problem. Part II: Matching.The first problem we consider in this part is the Linear Ordering Problem. We show how the linear program of this problem can be solved by using a primal-dual based combinatorial algorithm instead of the Simplex method. Next, we address the cyclical scheduling problem which is used to schedule shifts for workers in a factory. Given a set of n work periods, each worker is assigned a shift where he works for n-2 consecutive periods and takes off the remaining two periods. Thus, for n=7, a typical shift may be to work from Monday to Friday and take off Saturday and Sunday. Each shift may also have a cost associated with it. Furthermore, the factory requires that a given number of workers be available for each period (this requirement may vary from period to period). The objective is to assign a shift to each worker such that the daily requirement is fulfilled and the total cost of the shifts is minimized. We use the primal-dual method to solve the (n-2,n) cyclical scheduling problem by solving a series of b-matching problems on a cycle of n vertices.