We study the computational complexity of winner determination problems in approval-based committee elections under Thiele voting rules. These form a class of rules parameterized by a fixed weight vector that specifies how a voter's satisfaction depends on the number of approved candidates elected. We first analyze the structure of optimal solutions based on the sets of voters who approve each candidate---that is, how voters' approval ballots induce dependencies between candidates---revealing constraints on a winning committee under any fixed Thiele voting rule. Using this, we design FPT algorithms for Proportional Approval Voting (PAV) and other Thiele rules on a natural restricted domain known as the Voter Interval domain---that is, after a suitable ordering of voters, each candidate is approved by a consecutive interval of voters. In particular, we show that every Thiele rule on Voter Interval is FPT with respect to a parameter for which the problem is NP-hard on general instances, even when the parameter takes constant values. Our results advance the understanding of the computational complexity of PAV on Voter Interval instances, which remains one of the central open questions in this area. We further resolve two open questions from the literature on PAV (and other Thiele voting rules) by providing a polynomial-time algorithm for instances where each candidate is approved by at most two voters, and an FPT algorithm parameterized by the total score of a winning committee.

We consider ordinal scheduling on identical parallel machines with cardinality constraints. That is, a parameter k=1 is given such that no machine can contain more than k jobs. The objective is to assign the jobs to machines such that the makespan is minimized. In the ordinal setting, jobs are presented one by one and it is known that they arrive sorted by non-increasing sizes, but the specific sizes become known only after termination of the algorithm. An ordinal algorithm is compared to an optimal offline algorithm that knows all sizes, but it can also assign at most k jobs to each machine. Several simple algorithms achieve a competitive ratio of 2. In this work, we improve this ratio using a carefully designed algorithm.

We consider online scheduling with class constraints. That is, we are given $m$ machines, each with $k$ class slots. Upon receiving a job $j$ with class $c_j$, an algorithm needs to allocate $j$ on some machine $i$. The goal is to minimize the makespan while not assigning more than $k$ different classes onto each machine. While the offline case is well understood and even (E)PTAS results are known [Jansen, Lassota, Maack SPAA'20, Chen Jansen Luo Zhang COCOA'16], the online case admits strong impossibility results in classical competitive analysis [Epstein, Lassota, Levin, Maack, Rohwedder STACS'22]. We overcome these daunting results by investigating the problem in a learning-augmented setting where an algorithm can access possibly erroneous predictions. We present new algorithms with competitive ratios independent of $m$ and tight lower bounds for several classical and problem-specific prediction models. We thereby give a structured overview of what additional information helps in the design of better scheduling algorithms.

A cornerstone of social choice theory is Condorcet’s paradox which says that in an election where n voters rank m candidates it is possible that, no matter which candidate is declared the winner, a majority of voters would have preferred an alternative candidate. Instead, can we always choose a small committee of winning candidates that is preferred to any alternative candidate by a majority of voters? Elkind, Lang, and Saffidine raised this question and called such a committee a Condorcet winning set. They showed that winning sets of size 2 may not exist, but sets of size logarithmic in the number of candidates always do. In this work, we show that Condorcet winning sets of size 6 always exist, regardless of the number of candidates or the number of voters. More generally, we show that if α/1 − lnα ≥ 2/k + 1, then there always exists a committee of size k such that less than an α fraction of the voters prefer an alternate candidate. These are the first nontrivial positive results that apply for all k ≥ 2. Our proof uses the probabilistic method and the minimax theorem, inspired by recent work on approximately stable committee selection. We construct a distribution over committees that performs sufficiently well (when compared against any candidate on any small subset of the voters) so that this distribution must contain a committee with the desired property in its support.

We study two classic variants of block-structured integer programming. Two-stage stochastic programs are integer programs of the form {Aix + Diyi = bi for all i = 1,…, n}, where Ai and Di are bounded-size matrices. Intuitively, this form corresponds to the setting when after setting a small set of global variables x, the program can be decomposed into a possibly large number of bounded-size subprograms. On the other hand, n-fold programs are integer programs of the form and Diyi = bi for all i = 1,…,n}, where again Ci and Di are bounded-size matrices. This form is natural for knapsack-like problems, where we have a large number of variables partitioned into small-size groups, each group needs to obey some set of local constraints, and there are only a few global constraints that link together all the variables.

We consider non-clairvoyant scheduling with online precedence constraints, where an algorithm is oblivious to any job dependencies and learns about a job only if all of its predecessors have been completed. Given strong impossibility results in classical competitive analysis, we investigate the problem in a learning-augmented setting, where an algorithm has access to predictions without any quality guarantee. We discuss different prediction models: novel problem-specific models as well as general ones, which have been proposed in previous works. We present lower bounds and algorithmic upper bounds for different precedence topologies, and thereby give a structured overview on which and how additional (possibly erroneous) information helps for designing better algorithms. Along the way, we also improve bounds on traditional competitive ratios for existing algorithms.

We solve the Bin Packing problem in $O^*(2^k)$ time, where $k$ is the number of items less or equal to one third of the bin capacity. This parameter measures the distance from the polynomially solvable case of only large (i.e., greater than one third) items. Our algorithm is actually designed to work for a more general Vector Bin Packing problem, in which items are multidimensional vectors. We improve over the previous fastest $O^*(k! \cdot 4^k)$ time algorithm. Our algorithm works by reducing the problem to finding an exact weight perfect matching in a (multi-)graph with $O^*(2^k)$ edges, whose weights are integers of the order of $O^*(2^k)$. To solve the matching problem in the desired time, we give a variant of the classic Mulmuley-Vazirani-Vazirani algorithm with only a linear dependence on the edge weights and the number of edges, which may be of independent interest. Moreover, we give a tight lower bound, under the Strong Exponential Time Hypothesis (SETH), showing that the constant $2$ in the base of the exponent cannot be further improved for Vector Bin Packing. Our techniques also lead to improved algorithms for Vector Multiple Knapsack, Vector Bin Covering, and Perfect Matching with Hitting Constraints.

Makespan minimization on parallel identical machines is a classical and intensively studied problem in scheduling, and a classic example for online algorithm analysis with Graham’s famous list scheduling algorithm dating back to the 1960s. In this problem, jobs arrive over a list and upon an arrival, the algorithm needs to assign the job to a machine. The goal is to minimize the makespan, that is, the maximum machine load. In this paper, we consider the variant with an additional cardinality constraint: The algorithm may assign at most k jobs to each machine where k is part of the input. While the offline (strongly NP-hard) variant of cardinality constrained scheduling is well understood and an EPTAS exists here, no non-trivial results are known for the online variant. We fill this gap by making a comprehensive study of various different online models. First, we show that there is a constant competitive algorithm for the problem and further, present a lower bound of 2 on the competitive ratio of any online algorithm. Motivated by the lower bound, we consider a semi-online variant where upon arrival of a job of size p, we are allowed to migrate jobs of total size at most a constant times p. This constant is called the migration factor of the algorithm. Algorithms with small migration factors are a common approach to bridge the performance of online algorithms and offline algorithms. One can obtain algorithms with a constant migration factor by rounding the size of each incoming job and then applying an ordinal algorithm to the resulting rounded instance. With this in mind, we also consider the framework of ordinal algorithms and characterize the competitive ratio that can be achieved using the aforementioned approaches. More specifically, we show that in both cases, one can get a competitive ratio that is strictly lower than 2, which is the bound from the standard online setting. On the other hand, we prove that no PTAS is possible.

Assigning jobs onto identical machines with the objective to minimize the maximal load is one of the most basic problems in combinatorial optimization and has many practical applications in manufacturing, parallel computation, service industries among others. Motivated by its utilization in product planing and data placement we study a natural extension called Class Constrained Scheduling (CCS). In this problem each job additionally admits a class and each machine can only schedule jobs from at most c different classes for some number c. Even though this problem is closely related to the Class Constraint Bin Packing, the Class Constraint Knapsack and the Cardinality Constraint variants, CCS lacks results regarding approximation algorithms despite being also NP-hard. We fill this gap by analyzing the problem considering three different ways to feasibly allot the jobs: The non-preemptive case, where we have to place the jobs as a whole; the splittable case, where we are allowed to split and allot the jobs arbitrarily as long as they do not overlap on a machine; and finally the preemptive case, where jobs can be split but pieces belonging to the same job are not allowed to be scheduled in parallel. For each case we introduce the first PTAS where neither c nor the number of all classes have to be a constant. In order to achieve this goal, we give new insights about the structure of optimal solutions. In particular we prove that there always exists an optimal solution where the jobs are split evenly and the number of pieces for each job is bounded. Further these job pieces will be placed in just a few specific positions. Moreover, by preprocessing the instance appropriately, we manage to set up a configuration Integer Linear Program (ILP) with a specific form of the constraint matrix called N-fold ILP. These N-fold ILPs can then be solved efficiently. Additionally, we developed the first simple approximation algorithms with constant approximation ratios running in more efficient, polynomial time. The algorithm for the non-preemptive case has a ratio of 7/3 and a running time of O(n2 log(n) + n log2(pmax)). The splittable and the preemptive case admit algorithms with ratio~2 and a running time of O(n2 log(n)). All results also hold when the number of machines cannot be bounded by a polynomial in n.

We study an important case of integer linear programs (ILPs) of the form $\max\{c^Tx \ \vert\ \mathcal Ax = b, l \leq x \leq u,\, x \in \mathbb{Z}^{n t} \} $ with $n t$ variables and lower and upper bounds $\ell, u\in\mathbb Z^{nt}$. In $n$-fold ILPs nonzero entries only appear in the first $r$ rows of the matrix $\mathcal A$ and in small blocks of size $s\times t$ along the diagonal underneath. Despite this restriction, many optimization problems can be expressed in this form. It is known that $n$-fold ILPs are fixed-parameter tractable (FPT) regarding the parameters $s, r,$ and $\Delta$, where $\Delta$ is the greatest absolute value of any entry in $\mathcal A$. The state-of-the-art technique is a local search algorithm that subsequently moves in an improving direction where the number of iterations and the search for such an improving direction each take time $\Omega(n)$. This leads to a running time quadratic in $n$. We introduce a technique based on color coding which allows us to compute these improving directions in logarithmic time after a single initialization step. This yields an algorithm for $n$-fold ILPs with a running time that is near-linear in $nt$, the number of variables. More precisely, our algorithm runs in time $(rs\Delta)^{\mathcal{O}(r^2s + s^2)} L^2 nt \log^{\mathcal{O}(1)}(nt)$, where $L$ is the encoding length of the largest integer in the input. Further, in contrast to the algorithms in recent literature, we do not need to solve the LP relaxation in order to handle unbounded variables. Instead we give a structural lemma to introduce appropriate bounds. On the other hand, if we are given such an LP solution, the running time can be decreased by a factor of $L$.