A retailer is purchasing goods in bundles from suppliers and then selling these goods in bundles to customers; her goal is to maximize profit, which is the revenue obtained from selling goods minus the cost of purchasing those goods. In this paper, we study this general trading problem from the retailer's perspective, where both suppliers and customers arrive online. The retailer has inventory constraints on the number of goods from each type that she can store, and she must decide upon arrival of each supplier/customer which goods to buy/sell in order to maximize profit. We design an algorithm with logarithmic competitive ratio compared to an optimal offline solution. We achieve this via an exponential-weight-update dynamic pricing scheme, and our analysis dual fits the retailer's profit with respect to a linear programming formulation upper bounding the optimal offline profit. We prove (almost) matching lower bounds, and we also extend our result to an incentive compatible mechanism. Prior to our work, algorithms for trading bundles were known only for the special case of selling an initial inventory.

In the online sorting problem, we have an array $A$ of $n$ cells, and receive a stream of $n$ items $x_1,\dots,x_n\in [0,1]$. When an item arrives, we need to immediately and irrevocably place it into an empty cell. The goal is to minimize the sum of absolute differences between adjacent items, which is called the \emph{cost} of the algorithm. It has been shown by Aamand, Abrahamsen, Beretta, and Kleist (SODA 2023) that when the stream $x_1,\dots,x_n$ is generated adversarially, the optimal cost bound for any deterministic algorithm is $Θ(\sqrt{n})$. In this paper, we study the stochastic version of online sorting, where the input items $x_1,\dots,x_n$ are sampled uniformly at random. Despite the intuition that the stochastic version should yield much better cost bounds, the previous best algorithm for stochastic online sorting by Abrahamsen, Bercea, Beretta, Klausen and Kozma (ESA 2024) only achieves $\tilde{O}(n^{1/4})$ cost, which seems far from optimal. We show that stochastic online sorting indeed allows for much more efficient algorithms, by presenting an algorithm that achieves expected cost $\log n\cdot 2^{O(\log^* n)}$. We also prove a cost lower bound of $Ω(\log n)$, thus show that our algorithm is nearly optimal.

In the online sorting problem, a sequence of \(n\) numbers in \([0,1]\) (including \(\{0,1\}\)) have to be inserted in an array of size \(m \ge n\) so as to minimize the sum of absolute differences between pairs of numbers occupying consecutive non-empty cells. Previously, Aamand et al. (SODA~2023) gave a deterministic \(2^{\sqrt{\log n} \sqrt{\log\log n + \log(1/\varepsilon)}}\)-competitive algorithm when \(m = (1+\varepsilon)n\) for any \(\varepsilon \ge \Omega(\log n / n)\). They also showed a lower bound: with \(m = \gamma n\) space, the competitive ratio of any deterministic algorithm is at least \(1/\gamma \cdot \Omega(\log n / \log\log n)\). This left an exponential gap between the upper and lower bounds for the problem.

Heuristics on what online algorithms should do at any given time can give large improvements to the performance of the algorithm. Today, such heuristics are mostly generated by some machine learning algorithm that was trained on what is hoped to be a similar input. A heuristic can also be viewed as action predictions where, at each time step, the predictor tries to predict the action that an optimal algorithm would have taken. We consider the online packet scheduling problem where unit size packets arrive over time, each is associated with a value and a deadline. The goal is to schedule the packets to maximize the value of the packets transmitted by their deadline. We consider an arbitrary algorithm (heuristic) and robustify it without loss. Specifically, we provide an algorithm that is at least as good as the heuristic for any input, while guaranteeing it is 3-competitive regardless of the heuristic's performance. Finally, we show that it is not possible to be as good as the heuristic and remain constant-competitive if we consider the asynchronous model.