Thanos Tolias

Andreas Charalampopoulos, Dimitris Fotakis, Thanos Tolias

We study budget feasible procurement auctions, in which $n$ agents, each with a privately held service cost, offer their services to an employer. The employer seeks to maximize a public submodular valuation function over the set of hired agents, while facing a hard budget constraint. We consider an online posted-price setting, in which agents arrive in a uniformly random order (a.k.a. \emph{secretary arrivals}) and the employer must make irrevocable take-it-or-leave-it offers upon their arrival. The employer does not get any feedback about the agent service costs other than whether they accept the offer or not. We introduce Repeated Descent (a.k.a. \RED), a deterministic framework based on adaptive linear posted pricing. \RED enforces budget feasibility by adaptively adjusting its pricing and balancing each pricing level with the number of agents considered in it. Using \RED as the main building block, we obtain a $1046$-competitive posted-price mechanism for online budget feasible auctions with secretary agent arrivals and submodular valuations, thus improving on the previously best known ratio of (Charalampopoulos et al., EC 2025) by several orders of magnitude. Combining \RED with random subsampling, we obtain the first constant-competitive posted-price budget feasible mechanism for non-monotone submodular valuations. On the negative side, we show that every online budget feasible mechanism with XOS valuations has a competitive ratio of $Ω\!\left(\tfrac{\log n}{(\log\log n)^2}\right)$.

Sotiris Kanellopoulos, Giorgos Mitropoulos, Christos Pergaminelis et al.

The k-Visits problem is a recently introduced finite version of Pinwheel Scheduling [Kanellopoulos et al., SODA 2026]. Given the deadlines of n tasks, the problem asks whether there exists a schedule of length kn executing each task exactly k times, with no deadline expiring between consecutive visits (executions) of each task. In this work we prove that 2-Visits is strongly NP-complete even when the maximum multiplicity of the input is equal to 2, settling an open question from [Kanellopoulos et al., SODA 2026] and contrasting the tractability of 2-Visits for simple sets. On the other hand, we prove that 2-Visits is in RP when the number of distinct deadlines is constant, thus making progress on another open question regarding the parameterization of 2-Visits by the number of numbers. We then generalize all existing positive results for 2-Visits to a version of the problem where some tasks must be visited once and some other tasks twice, while providing evidence that some of these results are unlikely to transfer to 3-Visits. Lastly, we establish bounds for the density thresholds of k-Visits, analogous to the $(5/6)$-threshold of Pinwheel Scheduling [Kawamura, STOC 2024]; in particular, we show a $\sqrt{2}-1/2\approx 0.9142$ lower bound for the density threshold of 2-Visits and prove that the density threshold of k-Visits approaches $5/6\approx 0.8333$ for $k \to \infty$.

Dimitris Fotakis, Evangelia Gergatsouli, Themis Gouleakis et al.

We consider Online Facility Location in the framework of learning-augmented online algorithms. In Online Facility Location (OFL), demands arrive one-by-one in a metric space and must be (irrevocably) assigned to an open facility upon arrival, without any knowledge about future demands. We focus on uniform facility opening costs and present an online algorithm for OFL that exploits potentially imperfect predictions on the locations of the optimal facilities. We prove that the competitive ratio decreases from sublogarithmic in the number of demands $n$ to constant as the so-called $η_1$ error, i.e., the sum of distances of the predicted locations to the optimal facility locations, decreases. E.g., our analysis implies that if for some $\varepsilon > 0$, $η_1 = \mathrm{OPT} / n^\varepsilon$, where $\mathrm{OPT}$ is the cost of the optimal solution, the competitive ratio becomes $O(1/\varepsilon)$. We complement our analysis with a matching lower bound establishing that the dependence of the algorithm's competitive ratio on the $η_1$ error is optimal, up to constant factors. Finally, we evaluate our algorithm on real world data and compare the performance of our learning-augmented approach against the performance of the best known algorithm for OFL without predictions.