Condorcet winning sets address the Condorcet paradox by selecting a small set of candidates—rather than a single winner—such that a majority prefers no unselected alternative over all members of the set. This notion extends to \(\alpha\)-undominated sets, which require the same property to hold for any \(\alpha\)-fraction of voters. Such sets are guaranteed to exist with constant size for any fixed \(\alpha\). However, the requirement that an outsider be preferred to every member of the set can be overly restrictive and difficult to justify in many applications. Motivated by this, we introduce a more flexible notion: \((t, \alpha)\)-undominated sets. Here, each voter compares an outsider to their \(t\)-th most preferred member of the set, and the set is undominated if no outsider is preferred by more than an \(\alpha\)-fraction of voters. This framework subsumes prior definitions, recovering Condorcet winning sets when \((t = 1, \alpha = 1/2)\) and \(\alpha\)-undominated sets when \(t = 1\), and introduces a new, tunable notion of collective acceptability for \(t \gt 1\).

Abstract In the pairwise weighted spanner problem, we are given a directed graph with n vertices and k terminal vertex pairs. Each edge is assigned both a cost and a length . The goal is to find a minimum-cost subgraph in which the terminal distance constraints are satisfied. A more restricted variant of this problem was shown to be $$O(2^{{\log ^{1-\varepsilon } n}})$$ O ( 2 log 1 - ε n ) -hard to approximate under a standard complexity assumption, by Elkin and Peleg (Theory of Computing Systems, 2007). This general formulation captures many well-studied network connectivity problems, including spanners, distance preservers, and Steiner forests. For the weighted spanner problem where the edges have positive integral lengths with magnitudes polynomial in n , we show an $$\tilde{O}(n^{4/5 + \varepsilon })$$ O ~ ( n 4 / 5 + ε ) -approximation algorithm. When the edges have unit costs and lengths, the best previous algorithm gives an $$\tilde{O}(n^{3/5 + \varepsilon })$$ O ~ ( n 3 / 5 + ε ) -approximation, due to Chlamtáč, Dinitz, Kortsarz, and Laekhanukit (Transactions on Algorithms, 2020). We also consider the online setting, where the vertex pairs arrive one at a time, and edges must be added irrevocably to satisfy the distance constraints. We show an $$\tilde{O}(k^{1/2 + \varepsilon })$$ O ~ ( k 1 / 2 + ε ) -competitive algorithm. The state-of-the-art results are an $$\tilde{O}(n^{4/5})$$ O ~ ( n 4 / 5 ) -competitive algorithm when edges have unit costs and arbitrary positive lengths, and a $$\min \{\tilde{O}(k^{1/2 + \varepsilon }), \tilde{O}(n^{2/3 + \varepsilon })\}$$ min { O ~ ( k 1 / 2 + ε ) , O ~ (

\emph{Learning-augmented algorithms} have been extensively studied in the computer science community recently, particularly in the context of online problems, in which machine-learning predictors can help provide additional information about the future, in order to overcome classical impossibility results. Such algorithms use \emph{advice} prudently to improve the performance of classical algorithms, while ensuring robustness against inaccurate advice. In this paper, we present learning-augmented algorithmic frameworks for two fundamental optimizations settings, extending and generalizing prior works. For \emph{online packing with concave objectives}, we present a simple but overarching strategy that \emph{switches} between the advice and the state-of-the-art online algorithm. For \emph{online covering with convex objectives}, we greatly extend primal-dual methods for online convex covering programs and previous learning-augmented framework for online covering linear programs from the literature, to many new applications. We show that our algorithms break impossibility results when the advice is accurate, while maintaining comparable performance with state-of-the-art classical online algorithms even when the advice is erroneous.

We present a framework that unifies directed buy-at-bulk network design and directed spanner problems, namely, buy-at-bulk spanners. The goal is to find a minimum-cost routing solution for network design problems that captures economies at scale, while satisfying demands and distance constraints for terminal pairs. A more restricted version of this problem was shown to be O(2^{log^{1-ε} n})-hard to approximate, where n is the number of vertices, under a standard complexity assumption, by Elkin and Peleg (Theory of Computing Systems, 2007). Our results for buy-at-bulk spanners are the following. - When the edge lengths are integral with magnitude polynomial in n we present: 1) An Õ(n^{4/5 + ε})-approximation polynomial-time randomized algorithm for uniform demands. 2) An Õ(k^{1/2 + ε})-approximation polynomial-time randomized algorithm for general demands, where k is the number of terminal pairs. This can be improved to an Õ(k^{ε})-approximation algorithm for the single-source problem. The same approximation ratios hold in the online setting. - When the edge lengths are rational and well-conditioned, we present an Õ(k^{1/2 + ε})-approximation polynomial-time randomized algorithm that may slightly violate the distance constraints. The result can be improved to an Õ(k^ε)-approximation algorithm for the single-source problem. The same approximation ratios hold for the online setting when the condition number is given in advance. To the best of our knowledge, these are the first sublinear factor approximation algorithms for directed buy-at-bulk spanners. We allow the edge lengths to be negative and the demands to be non-unit, unlike the previous literature. Our approximation ratios match the state-of-the-art ratios in special cases, namely, buy-at-bulk network design by Antonakopoulos (WAOA, 2010) and (online) weighted spanners by Grigorescu, Kumar, and Lin (APPROX 2023). Furthermore, we improve the competitive ratio for online buy-at-bulk by Chakrabarty, Ene, Krishnaswamy, and Panigrahi (SICOMP, 2018) by a factor of log R, where R is the ratio between the maximum demand and the minimum demand.

Semidefinite programming (SDP) is a unifying framework that generalizes both linear programming and quadratically-constrained quadratic programming, while also yielding efficient solvers, both in theory and in practice. However, there exist known impossibility results for approximating the optimal solution when constraints for covering SDPs arrive in an online fashion. In this paper, we study online covering linear and semidefinite programs in which the algorithm is augmented with advice from a possibly erroneous predictor. We show that if the predictor is accurate, we can efficiently bypass these impossibility results and achieve a constant-factor approximation to the optimal solution, i.e., consistency. On the other hand, if the predictor is inaccurate, under some technical conditions, we achieve results that match both the classical optimal upper bounds and the tight lower bounds up to constant factors, i.e., robustness. More broadly, we introduce a framework that extends both (1) the online set cover problem augmented with machine-learning predictors, studied by Bamas, Maggiori, and Svensson (NeurIPS 2020), and (2) the online covering SDP problem, initiated by Elad, Kale, and Naor (ICALP 2016). Specifically, we obtain general online learning-augmented algorithms for covering linear programs with fractional advice and constraints, and initiate the study of learning-augmented algorithms for covering SDP problems. Our techniques are based on the primal-dual framework of Buchbinder and Naor (Mathematics of Operations Research, 34, 2009) and can be further adjusted to handle constraints where the variables lie in a bounded region, i.e., box constraints.

We present online algorithms for directed spanners and Steiner forests. These problems fall under the unifying framework of online covering linear programming formulations, developed by Buchbinder and Naor (MOR, 34, 2009), based on primal-dual techniques. Our results include the following: For the pairwise spanner problem, in which the pairs of vertices to be spanned arrive online, we present an efficient randomized $\tilde{O}(n^{4/5})$-competitive algorithm for graphs with general lengths, where $n$ is the number of vertices. With uniform lengths, we give an efficient randomized $\tilde{O}(n^{2/3+ε})$-competitive algorithm, and an efficient deterministic $\tilde{O}(k^{1/2+ε})$-competitive algorithm, where $k$ is the number of terminal pairs. These are the first online algorithms for directed spanners. In the offline setting, the current best approximation ratio with uniform lengths is $\tilde{O}(n^{3/5 + ε})$, due to Chlamtac, Dinitz, Kortsarz, and Laekhanukit (TALG 2020). For the directed Steiner forest problem with uniform costs, in which the pairs of vertices to be connected arrive online, we present an efficient randomized $\tilde{O}(n^{2/3 + ε})$-competitive algorithm. The state-of-the-art online algorithm for general costs is due to Chakrabarty, Ene, Krishnaswamy, and Panigrahi (SICOMP 2018) and is $\tilde{O}(k^{1/2 + ε})$-competitive. In the offline version, the current best approximation ratio with uniform costs is $\tilde{O}(n^{4/7 + ε})$, due to Abboud and Bodwin (SODA 2018). A small modification of the online covering framework by Buchbinder and Naor implies a polynomial-time primal-dual approach with separation oracles, which a priori might perform exponentially many calls. We convert the online spanner problem and the online Steiner forest problem into online covering problems and round in a problem-specific fashion.

With COVID 19 prevalent in the USA and the world, efficient social distance seating became an option for sports venues. The social distancing constraint requires six feet between individuals when the game has live audiences. Depending on the seats' dimensions, this would translate to a certain number of empty rows and empty seats in a row between the individuals. As a result, it is not possible to seat all ticket holders with safe social distancing. Hence, it necessitates reassigning spectators to games. An important feature of this problem is that season tickets are grouped by family, and only a safe distance between two different families needs to be maintained. Members of the same family can sit next to each other. Therefore, a large family needs fewer empty seats per person to maintain social distancing. A football season has about six home games. If priority is given to larger families for all the games, then many people can watch the live games, but the outcome will be highly unfair. Striking a good balance between efficiency and fairness is a nontrivial task.

A heapable sequence is a sequence of numbers that can be arranged in a min-heap data structure. Finding a longest heapable subsequence of a given sequence was proposed by Byers, Heeringa, Mitzenmacher, and Zervas (ANALCO 2011) as a generalization of the well-studied longest increasing subsequence problem and its complexity still remains open. An equivalent formulation of the longest heapable subsequence problem is that of finding a maximum-sized binary tree in a given permutation directed acyclic graph (permutation DAG). In this work, we study parameterized algorithms for both longest heapable subsequence and maximum-sized binary tree. We introduce alphabet size as a new parameter in the study of computational problems in permutation DAGs and show that this parameter with respect to a fixed topological ordering admits a complete characterization and a polynomial time algorithm. We believe that this parameter is likely to be useful in the context of optimization problems defined over permutation DAGs.

A heapable sequence is a sequence of numbers that can be arranged in a min-heap data structure. Finding a longest heapable subsequence of a given sequence was proposed by Byers, Heeringa, Mitzenmacher, and Zervas (ANALCO 2011) as a generalization of the well-studied longest increasing subsequence problem and its complexity still remains open. An equivalent formulation of the longest heapable subsequence problem is that of finding a maximum-sized binary tree in a given permutation directed acyclic graph (permutation DAG). In this work, we study parameterized algorithms for both longest heapable subsequence and maximum-sized binary tree. We introduce alphabet size as a new parameter in the study of computational problems in permutation DAGs and show that this parameter with respect to a fixed topological ordering admits a complete characterization and a polynomial time algorithm. We believe that this parameter is likely to be useful in the context of optimization problems defined over permutation DAGs.