We consider assortment and inventory planning problems with dynamic stockout-based substitution effects, and without replenishment, in two different settings: (1) Customers can see all available products when they arrive, a typical scenario in physical stores. (2) The seller can choose to offer a subset of available products to each customer, which is more common on online platforms. Both settings are known to be computationally challenging, and the current approximation algorithms for the two settings are quite different. We develop a unified algorithm framework under the MNL choice model for both settings. Our algorithms improve on the state-of-the-art algorithms in terms of approximation guarantee and runtime, and the ability to manage uncertainty in the total number of customers and handle more complex constraints. In the process, we establish various novel properties of dynamic assortment planning (for the MNL choice model) that may be useful more broadly. A full version of this paper can be found at https://arxiv.org/abs/2404.03604.

Simplicity Meets Optimality in Online Resource Allocation Online platforms frequently manage sequential allocation decisions where outcomes are uncertain, such as selecting which products to display to a user. While it is often assumed that complex “adaptive” algorithms—those reacting to real-time feedback like user choices—are necessary for optimal performance, Rajan Udwani’s paper, “Optimality of Nonadaptive Algorithms in Online Submodular Welfare Maximization with Stochastic Outcomes,” challenges this assumption. The paper introduces a general framework and a “lifting” technique that translates established results from deterministic settings to those involving stochastic outcomes. Using this framework, Udwani demonstrates that nonadaptive Greedy-like algorithms, which remain oblivious to specific outcome realizations, achieve the best possible competitive ratios across diverse settings and arrival models. The findings suggest that for a broad class of objectives, including submodular functions, adaptivity offers no theoretical advantage. This allows for the use of simpler, more robust algorithms in environments where outcomes may be delayed or difficult to monitor.

We define a new class of set functions that in addition to being monotone and subadditive, also admit a very limited form of submodularity defined over a permutation of the ground set. We refer to this permutation as a submodular order. We give fast algorithms with strong approximation guarantees for maximizing submodular order functions under a variety of constraints. Applying this new notion to the problem of constrained assortment optimization in fundamental choice models, we obtain new algorithms that are both faster and have stronger approximation guarantees (in some cases, first algorithm with constant factor guarantee). We also show an intriguing connection to the maximization of monotone submodular functions in the streaming model, where we recover best known approximation guarantees as a corollary of our results.

We present a new combinatorial bandit model, the \textit{cascading contextual assortment bandit}. This model serves as a generalization of both existing cascading bandits and assortment bandits, broadening their applicability in practice. For this model, we propose our first UCB bandit algorithm, UCB-CCA. We prove that this algorithm achieves a $T$-step regret upper-bound of $\tilde{\mathcal{O}}(\frac{1}{\kappa}d\sqrt{T})$, sharper than existing bounds for cascading contextual bandits by eliminating dependence on cascade length $K$. To improve the dependence on problem-dependent constant $\kappa$, we introduce our second algorithm, UCB-CCA+, which leverages a new Bernstein-type concentration result. This algorithm achieves $\tilde{\mathcal{O}}(d\sqrt{T})$ without dependence on $\kappa$ in the leading term. We substantiate our theoretical claims with numerical experiments, demonstrating the practical efficacy of our proposed methods.

We consider a variation of the classic Adwords problem where the online algorithm does not know the advertisers' budgets a priori and the budget of an advertiser is revealed to the algorithm only when it is exceeded. A naïve greedy algorithm is 0.5 competitive for this setting and finding an algorithm with better performance remained an open problem. We show that no deterministic algorithm has competitive ratio better than 0.5 and give the first (randomized) algorithm with strictly better performance guarantee. We show that the competitive ratio of our algorithm is at least 0.522 but also strictly less than (1 − 1/e). We present novel applications of budget oblivious algorithms in search ads and beyond. In particular, we show that our algorithm achieves the best possible performance guarantee for deterministic online matching in the presence of multi-channel traffic.

We consider a generalization of the vertex weighted online bipartite matching problem where the offline vertices, called resources, are reusable. In particular, when a resource is matched it is unavailable for a deterministic time duration d after which it becomes available for a re-match. Thus, a resource can be matched to many different online vertices over a period of time.

In the paper “Online Matching with Stochastic Rewards: Optimal Competitive Ratio via Path-Based Formulation,” the authors develop a novel algorithm analysis approach to address stochastic elements in online matching. The approach leads to several new results that were previously out of reach for a fundamental generalization of online matching. More generally, the approach is useful for analyzing the performance of online algorithms for matching in settings with stochastic uncertainty that manifests after matching decisions are made.

Designing simple appointment systems that under uncertainty in service times, try to achieve both high utilization of expensive medical equipment and personnel as well as short waiting time for patients, has long been an interesting and challenging problem in health care. We consider a robust version of the appointment scheduling problem, introduced by Mittal et al. (2014), with the goal of finding simple and easy-to-use algorithms. Previous work focused on the special case where per-unit costs due to under-utilization of equipment/personnel are homogeneous i.e., costs are linear and identical. We consider the heterogeneous case and devise an LP that has a simple closed-form solution. This solution yields the first constant-factor approximation for the problem. We also find special cases beyond homogeneous costs where the LP leads to closed form optimal schedules. Our approach and results extend more generally to convex piece-wise linear costs. For the case where the order of patients is changeable, we focus on linear costs and show that the problem is strongly NP-hard when the under-utilization costs are heterogeneous. For changeable order with homogeneous under-utilization costs, it was previously shown that an EPTAS exists. We instead find an extremely simple, ratio-based ordering that is 1.0604 approximate.

We consider the problem of multi-objective maximization of monotone submodular functions subject to cardinality constraint, often formulated as $\max_{|A|=k}\min_{i\in\{1,\dots,m\}}f_i(A)$. While it is widely known that greedy methods work well for a single objective, the problem becomes much harder with multiple objectives. In fact, Krause et al.\ (2008) showed that when the number of objectives $m$ grows as the cardinality $k$ i.e., $m=\Omega(k)$, the problem is inapproximable (unless $P=NP$). On the other hand, when $m$ is constant Chekuri et al.\ (2010) showed a randomized $(1-1/e)-\epsilon$ approximation with runtime (number of queries to function oracle) $n^{m/\epsilon^3}$. %In fact, the result of Chekuri et al.\ (2010) is for the far more general case of matroid constant. We focus on finding a fast and practical algorithm that has (asymptotic) approximation guarantees even when $m$ is super constant. We first modify the algorithm of Chekuri et al.\ (2010) to achieve a $(1-1/e)$ approximation for $m=o(\frac{k}{\log^3 k})$. This demonstrates a steep transition from constant factor approximability to inapproximability around $m=\Omega(k)$. Then using Multiplicative-Weight-Updates (MWU), we find a much faster $\tilde{O}(n/\delta^3)$ time asymptotic $(1-1/e)^2-\delta$ approximation. While the above results are all randomized, we also give a simple deterministic $(1-1/e)-\epsilon$ approximation with runtime $kn^{m/\epsilon^4}$. Finally, we run synthetic experiments using Kronecker graphs and find that our MWU inspired heuristic outperforms existing heuristics.

In the directed single-source reachability problem, input is a directed graph G=(V, E) and a source node s, and the objective is to identify nodes t for which there is a directed path in G from s to t. Recently Nanongkai[STOC'14] presented a distributed algorithm that solves this problem in Õ(D+√nD1/2) rounds, where D and n respectively denote the network diameter and the number of nodes. This note presents an algorithm that slightly improves the round complexity to Õ(D+√nD1/4), thus getting closer to the ~Ω(D+√n) lower bound of Das Sarma et al.[STOC'11]

Supporting real-time applications is paramount to sustaining the growth of wireless networks. Real time applications require strict delay guarantee, i.e., a packet delayed beyond certain predefined value is dropped. Fortunately, depending on the codec used, real-time applications can sustain some loss gracefully. Aim of an admission control algorithm is to make sure that when a new flow is admitted, its and other existing flows' packet loss on account of deadline violation is below their respective acceptable limit. The problem of admission control has been studied extensively for wireline networks. However, this analysis does not extend to wireless case on account of fading. Here, we consider a wireless network with TDMA based MAC, and for this network obtain a scalable admission control algorithm.