@PhdThesis{diss_mods_00026125, author = {Rohwedder, Lars}, title = {Algorithms for Integer Programming and Allocation}, year = {2019}, publisher = {Christian-Albrechts-Universit{\"a}t zu Kiel}, address = {Kiel}, keywords = {restricted assignment; graph balancing; integer programming; configuration LP; local search; n-fold; MILP}, abstract = {The first part of the thesis contains pseudo-polynomial algorithms for integer linear programs (ILP). When certain parameters of an ILP are fixed, that is, they are treated as constants in the running time, it is possible to obtain algorithms with a running time that is pseudo-polynomial in the entries of the ILP's matrix. We present a tight pseudo-polynomial running time for ILPs with a constant number of constraints. Furthermore, we study an extension of this model to MILPs (linear programs that contain both fractional and integer variables). Then we move to n-fold ILPs, a class of ILPs with block structured matrices. We present the first algorithm for n-folds, which is near-linear in the dimensions of the ILP. The second part is about scheduling in non-identical machine models, more precisely, restricted allocation problems. Here a set of jobs has to be allocated to a set of machines. However, every job has a subset of machines and may only be assigned to a machine from this subset. We consider the objectives of minimizing the makespan or maximizing the minimum load. We study the integrality gap of a particularly strong linear programming relaxation, the configuration LP, for variations of this problem. The integrality gap can be seen as a measure of strength of an LP relaxation. A local search technique can be used to bound this value. However, the proofs are generally non-constructive, i.e., they do not give an efficient approximation algorithm right away. We derive better upper bounds on the integrality gap of the problems Restricted Assignment, Restricted Santa Claus, and Graph Balancing. Furthermore, we give the first (constructive) quasi-polynomial time approximation algorithm for Restricted Assignment with an approximation ratio strictly less than 2.}, url = {https://macau.uni-kiel.de/receive/diss_mods_00026125}, file = {:https://macau.uni-kiel.de/servlets/MCRFileNodeServlet/dissertation_derivate_00008487/Lars-Rohwedder.pdf:PDF}, language = {en} }