Zobrazeno 1 - 10
of 34
pro vyhledávání: '"Lassota, Alexandra"'
A Condorcet winning set is a set of candidates such that no other candidate is preferred by at least half the voters over all members of the set. The Condorcet dimension, which is the minimum cardinality of a Condorcet winning set, is known to be at
Externí odkaz:
http://arxiv.org/abs/2410.09201
We study the computational complexity of fairly allocating indivisible, mixed-manna items. For basic measures of fairness, this problem is hard in general. Thus, research has flourished concerning input classes where efficient algorithms exist, both
Externí odkaz:
http://arxiv.org/abs/2409.04225
Autor:
Hunkenschröder, Christoph, Klein, Kim-Manuel, Koutecký, Martin, Lassota, Alexandra, Levin, Asaf
We study fundamental block-structured integer programs called tree-fold and multi-stage IPs. Tree-fold IPs admit a constraint matrix with independent blocks linked together by few constraints in a recursive pattern; and transposing their constraint m
Externí odkaz:
http://arxiv.org/abs/2402.17290
We study two classic variants of block-structured integer programming. Two-stage stochastic programs are integer programs of the form $\{A_i \mathbf{x} + D_i \mathbf{y}_i = \mathbf{b}_i\textrm{ for all }i=1,\ldots,n\}$, where $A_i$ and $D_i$ are boun
Externí odkaz:
http://arxiv.org/abs/2311.01890
Let $d$ be a positive integer. For a finite set $X \subseteq \mathbb{R}^d$, we define its integer cone as the set $\mathsf{IntCone}(X) := \{ \sum_{x \in X} \lambda_x \cdot x \mid \lambda_x \in \mathbb{Z}_{\geq 0} \} \subseteq \mathbb{R}^d$. Goemans a
Externí odkaz:
http://arxiv.org/abs/2307.00406
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 class
Externí odkaz:
http://arxiv.org/abs/2301.12863
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
Externí odkaz:
http://arxiv.org/abs/2203.10077
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 pr
Externí odkaz:
http://arxiv.org/abs/2201.05113
An influential 1990 paper of Hochbaum and Shanthikumar made it common wisdom that "convex separable optimization is not much harder than linear optimization" [JACM 1990]. We exhibit two fundamental classes of mixed integer (linear) programs that run
Externí odkaz:
http://arxiv.org/abs/2111.08048
This paper considers parallel machine scheduling with incompatibilities between jobs. The jobs form a graph and no two jobs connected by an edge are allowed to be assigned to the same machine. In particular, we study the case where the graph is a col
Externí odkaz:
http://arxiv.org/abs/2011.06150