José A. Soto

Ricardo Arancibia-Castillo, José A. Soto

We study a single-machine scheduling problem in which each job $j$ has a nonnegative processing time $p_j\ge 0$ and a due date $d_j\in\mathbb{R}$. For a non-idling schedule $S$, let $C_j(S)$ be the completion time and let $L_j(S)=C_j(S)-d_j$ be the (possibly negative) lateness. The objective is to minimize the sum of the $k$ largest lateness values, interpolating between maximum lateness ($k=1$) and total lateness ($k=n$). We prove that the decision version is weakly NP-complete when $k$ is part of the input. For fixed $k$, we give an $O(k^2 n^{k+2})$ algorithm. As a consequence, we resolve a conjecture of Woeginger on the top-$k$ tardiness problem and obtain an $O(n^{k+2})$ algorithm for every fixed $k$. Our main structural result shows that there exists an optimal schedule that admits a block-island decomposition. Outside a suitable top-$k$ set, jobs form due-date blocks ordered by due date. Within each due-date class, the top-$k$ jobs form a suffix in lexicographic shortest-processing-time (SPT) order. This structure also yields an FPT algorithm parameterized by $D+k$, where $D$ is the number of distinct due dates. Independently, a standard dual representation of the top-$k$ objective reduces the problem to a family of total-tardiness instances with uniformly shifted due dates. For integral data, this gives a pseudopolynomial algorithm and a fully polynomial additive approximation scheme with error at most $\varepsilon M$, where $M=\max\{1,\max_j p_j,\max_j |d_j|\}$. The same route also gives XP algorithms for fixed $P$ and fixed $D$, where $P$ is the number of distinct processing times.

Kristóf Bérczi, Vasilis Livanos, José A. Soto et al.

The Matroid Secretary Problem is a central question in online optimization, modeling sequential decision-making under combinatorial constraints. We introduce a bipartite graph framework that unifies and extends several known formulations, including bipartite matching, matroid intersection, and matroid secretary problems. In this model, agents and items form a bipartite graph, and the objective is to select a matching that satisfies independence constraints on both sides. We first study the free-order setting under edge-arrivals. For $k$-matroid intersection, we leverage a core lemma by [FSZ, 2022] to design an $Ω(1/k^2)$-competitive algorithm, extending known results for single matroids. Building on this, we introduce $k$-growth systems -- a new class of independence systems that lie properly between $k$-matchoids and $k$-extendible systems and may be of independent combinatorial interest. We establish a generalized core lemma for $k$-growth systems, showing that a suitably defined set of critical elements retains a $Ω(1/k^2)$ fraction of the optimal weight. Using this lemma, we extend our $Ω(1/k^2)$-competitive algorithm to $k$-growth systems. We then study the agent-arrival model, which presents unique challenges to our framework. We extend the core lemma to this model and then apply it to obtain an $Ω(β/k^2)$-competitive algorithm for $k$-growth systems, where $β$ denotes the competitiveness of an appropriate type of order-oblivious algorithm for the item-side constraint. Finally, we extend our results to the case of multiple item selection, and obtain constant-competitive algorithms for fundamental cases such as partition matroids and $k$-matching constraints. We also study the closure properties and structural role and of $k$-growth systems within the hierarchy of $k$-systems.

Matías Ortiz-Angel, José A. Soto

We introduce and study the multiple-choice matroid secretary problem, denoted $(J,κ)$-MSP. For rank-one matroids and $κ=\infty$, it reduces to the classical secretary problem with $J$ choices. Elements arrive in uniformly random order. Algorithms may keep a candidate pool $\mathrm{AUX}$ feasible in the $J$-fold union matroid $\mathcal{M}^{(J)}$ satisfying $|\mathrm{AUX}|\le κ\cdot\mathrm{rank}(\mathcal{M})$. Finally, one extracts the maximum-weight independent subset of $\mathrm{AUX}$ in $\mathcal{M}$. This model separates online storage from the final feasible solution. We study two multiple-choice implementations: multi-track algorithms (maintaining $J$ independent sets of $\mathcal{M}$) and union-based algorithms (maintaining the pool directly in $\mathcal{M}^{(J)}$). Our main result is an exact optimal algorithm for transversal matroids in the uncapacitated $(J,\infty)$ setting. For fixed $J$, its probability-competitive ratio equals the optimal success probability of the classical $J$-choice secretary problem. Thus, rank-one instances are the worst case for the whole transversal class, and the optimal guarantee converges exponentially fast to $1$ as $J$ grows. We also analyze a simple single-threshold routing algorithm for capacitated transversal matroids with local capacities $b$ and global capacity $κ\cdot\mathrm{rank}(\mathcal{M})$. Its analysis provides explicit finite-parameter bounds and asymptotic formulas, showing how finite-rank loss caused by global capacity decays, and how $b$, $J$, and $κ$ interact. Finally, we instantiate the multi-track approach for $k$-column-sparse matroids (guarantee $1-O(e^{-J/(ke)})$) and the union-based approach for laminar matroids (guarantee $1-O(e^{-J/e})$).