Author name cluster

Alexandra Lassota

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers

2 author rows

AAAI Conference 2026 Conference Paper

Algorithms for Structured Elections Under Thiele Voting Rules

Alexandra Lassota
Krzysztof Sornat

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.

PDF Details DOI

ICLR Conference 2025 Conference Paper

Minimalistic Predictions for Online Class Constraint Scheduling

Dorian Guyot
Alexandra Lassota

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.

Details

STOC Conference 2025 Conference Paper

Six Candidates Suffice to Win a Voter Majority

Moses Charikar
Alexandra Lassota
Prasanna Ramakrishnan
Adrian Vetta
Kangning Wang 0001

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.

Details

IJCAI Conference 2024 Conference Paper

Aggregation of Continuous Preferences in One Dimension

Alberto Del Pia
Dušan Knop
Alexandra Lassota
Krzysztof Sornat
Nimrod Talmon

We develop a general, formal model of social choice in which voters have continuous preferences over a one-dimensional space. Our model is parameterized by different restrictions that we introduce regarding the way voter preferences change in time as well as the optimization criteria (that correspond to a normative continuum of fairness definitions) desired from an aggregation method---that outputs a continuous, one-dimensional curve---given such inputs. We discuss the applicability of the model to different real-world situations and, as a first step towards an analysis of the different model realizations, we concentrate on identifying those cases that are computationally feasible to compute.

PDF Details DOI

SODA Conference 2024 Conference Paper

Parameterized algorithms for block-structured integer programs with large entries

Jana Cslovjecsek
Martin Koutecký
Alexandra Lassota
Michal Pilipczuk
Adam Polak 0001

We study two classic variants of block-structured integer programming. Two-stage stochastic programs are integer programs of the form { A i x + D i y i = b i for all i = 1, …, n }, where A i and D i 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 D i y i = b i for all i = 1, …, n }, where again C i and D i 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. A line of recent work established that the optimization problem for both two-stage stochastic programs and n -fold programs is fixed-parameter tractable when parameterized by the dimensions of relevant matrices A i, C i, D i, and by the maximum absolute value of any entry appearing in the constraint matrix. A fundamental tool used in these advances is the notion of the Graver basis of a matrix, and this tool heavily relies on the assumption that all the entries of the constraint matrix are bounded. In this work, we prove that the parameterized tractability results for two-stage stochastic and n -fold programs persist even when one allows large entries in the global part of the program. More precisely, we prove the following: In this work, we prove that the parameterized tractability results for two-stage stochastic and n -fold programs persist even when one allows large entries in the global part of the program. More precisely, we prove the following: • The feasibility problem for two-stage stochastic programs is fixed-parameter tractable when parameterized by the dimensions of matrices A i, D i and by the maximum absolute value of the entries of matrices D i. That is, we allow matrices A i to have arbitrarily large entries. • The linear optimization problem for n -fold integer programs that are uniform - all matrices C i are equal - is fixed-parameter tractable when parameterized by the dimensions of matrices C i and D i and by the maximum absolute value of the entries of matrices D i. That is, we require that C i = C for all i = 1, …, n, but we allow C to have arbitrarily large entries. In the second result, the uniformity assumption is necessary; otherwise the problem is NP -hard already when the parameters take constant values. Both our algorithms are weakly polynomial: the running time is measured in the total bitsize of the input. In both results, we depart from the approach that relies purely on Graver bases. Instead, for two-stage stochastic programs, we devise a reduction to integer programming with a bounded number of variables using new insights about the combinatorics of integer cones. For n -fold programs, we reduce a given n -fold program to an exponential-size program with bounded right-hand sides, which we consequently solve using a reduction to mixed integer programming with a bounded number of integral variables. * The full version of the paper can be accessed at https: //arxiv. org/abs/2311. 01890. Martin Koutecky was partially supported by Charles University project UNCE/SCI/004 and by the project 22-22997S of GA ČR. The work of Michał Pilipczuk on this manuscript is a part of a project that has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme, Grant Agreement No 948057 — BOBR. Part of this work was done when Adam Polak and Alexandra Lassota were at École Polytechnique Fédérale de Lausanne, supported by the Swiss National Science Foundation projects Lattice Algorithms and Integer Programming (185030) and Complexity of Integer Programming (CRFS-2_207365). Part of this work was carried out while Alexandra Lassota was affiliated with Max Planck Institute for Informatics, SIC, Saarbrücken, Germany.

Details

ICML Conference 2023 Conference Paper

Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints

Alexandra Lassota
Alexander Lindermayr
Nicole Megow
Jens Schlöter

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.

Details

ICAPS Conference 2021 Conference Paper

Total Completion Time Minimization for Scheduling with Incompatibility Cliques

Klaus Jansen
Alexandra Lassota
Marten Maack
Tytus Pikies

This paper considers parallel machine scheduling with incompatibilities between jobs. The jobs form a graph equivalent to a collection of disjoint cliques. No two jobs in a clique are allowed to be assigned to the same machine. Scheduling with incompatibilities between jobs represents a well-established line of research in scheduling theory and the case of disjoint cliques has received increasing attention in recent years. While the research up to this point has been focused on the makespan objective, we broaden the scope and study the classical total completion time criterion. In the setting without incompatibilities, this objective is well-known to admit polynomial time algorithms even for unrelated machines via matching techniques. We show that the introduction of incompatibility cliques results in a richer, more interesting picture. We prove that scheduling on identical machines remains solvable in polynomial time, while scheduling on unrelated machines becomes APX-hard. Next, we study the problem under the paradigm of fixed-parameter tractable algorithms (FPT). In particular, we consider a problem variant with assignment restrictions for the cliques rather than the jobs. We prove that, despite still being APX-hard, it can be solved in FPT time with respect to the number of cliques. Moreover, we show that the problem on unrelated machines can be solved in FPT time for reasonable parameters, in particular, the parameter combination: maximum processing time, number of job kinds, and number of machines or maximum processing time, number of job kinds, and number of cliques. The latter results are extensions of known results for the case without incompatibilities, and can even be further extended to the case of total weighted completion time. All of the FPT results make use of n-fold Integer Programs that recently received great attention by proving their usefulness for scheduling problems.

Details

MFCS Conference 2020 Conference Paper

Solving Packing Problems with Few Small Items Using Rainbow Matchings

Max Bannach
Sebastian Berndt 0001
Marten Maack
Matthias Mnich
Alexandra Lassota
Malin Rau
Malte Skambath

An important area of combinatorial optimization is the study of packing and covering problems, such as Bin Packing, Multiple Knapsack, and Bin Covering. Those problems have been studied extensively from the viewpoint of approximation algorithms, but their parameterized complexity has only been investigated barely. For problem instances containing no "small" items, classical matching algorithms yield optimal solutions in polynomial time. In this paper we approach them by their distance from triviality, measuring the problem complexity by the number k of small items. Our main results are fixed-parameter algorithms for vector versions of Bin Packing, Multiple Knapsack, and Bin Covering parameterized by k. The algorithms are randomized with one-sided error and run in time 4^k⋅ k! ⋅ n^{O(1)}. To achieve this, we introduce a colored matching problem to which we reduce all these packing problems. The colored matching problem is natural in itself and we expect it to be useful for other applications. We also present a deterministic fixed-parameter algorithm for Bin Covering with run time O((k!)² ⋅ k ⋅ 2^k ⋅ n log(n)).

Details