Search

Motivated by applications in the gig economy, we study approximation algorithms for a sequential pricing problem. The input is a bipartite graph G=(I,J,E) between individuals I and jobs J. The platform has a value of vj for matching job j to an individual worker. In order to find a matching, the platform can consider the edges (ij)∈E in any order and make a one-time take-it-or-leave-it offer of a price πij=w of its choosing to i for completing j. The worker accepts the offer with a known probability pijw; in this case, the job and the worker are irrevocably matched. What is the best way to make offers to maximize revenue and/or social welfare? The optimal algorithm is known to be NP-hard to compute (even if there is only a single job). With this in mind, we design efficient approximations to the optimal policy via a new random-order online contention resolution scheme (RO-OCRS) for matching. Our main result is a 0.456-balanced RO-OCRS in bipartite graphs and a 0.45-balanced RO-OCRS in general graphs. These algorithms improve on the recent bound of 12(1−e−2)≈0.432 and improve on the best-known lower bounds for the correlation gap of matching, despite applying to a significantly more restrictive setting. As a consequence of our online contention resolution scheme results, we obtain a 0.456-approximate algorithm for the sequential pricing problem. We further extend our results to settings where workers can only be contacted a limited number of times and show how to achieve improved results for this problem via improved algorithms for the well-studied stochastic probing problem. Funding: This work was supported by the National Science Foundation [Grant CCF2209520] and a gift from Amazon Research. [ABSTRACT FROM AUTHOR]

Experimentation is prevalent in online marketplaces and social networks to assess the effectiveness of new market intervention. To mitigate the interference among users in an experiment, a common practice is to use a cluster-based experiment, where the designer partitions the market into loosely connected clusters and assigns all users in the same cluster to the same variant (treatment or control). Given the experiment, we assume an unbiased Horvitz–Thompson estimator is used to estimate the total market effect of the treatment. We consider the optimization problem of choosing (correlated) randomized assignments of clusters to treatment and control to minimize the worst-case variance of the estimator under a constraint that the marginal assignment probability is q∈(0,1) for all clusters. This problem can be formulated as a linear program where both the number of decision variables and constraints are exponential in the number of clusters—and hence is generally computationally intractable. We develop a family of practical experiments that we refer to as independent block randomization (IBR) experiments. Such an experiment partitions clusters into blocks so that each block contains clusters of similar size. It then treats a fraction q of the clusters in each block (chosen uniformly at random) and does so independently across blocks. The optimal cluster partition can be obtained in a tractable way using dynamic programming. We show that these policies are asymptotically optimal when the number of clusters grows large and no cluster size dominates the rest. In the special case where cluster sizes take values in a finite set and the number of clusters of each size is a fixed proportion of the total number of clusters, the loss is only a constant that is independent of the number of clusters. Beyond the asymptotic regime, we show that the IBR experiment has a good approximation for any problem instance when q is not very tiny. We also examine the performance of the IBR experiments on data-driven numerical examples, including examples based on Airbnb and Facebook data. This paper was accepted by Itai Ashlagi, revenue management and market analytics. Funding: O. Candogan acknowledges NSF [Award 2216912] for "Institute for Data, Econometrics, Algorithms and Learning." Supplemental Material: The online appendix is available at https://doi.org/10.1287/mnsc.2021.02741. [ABSTRACT FROM AUTHOR]

This paper considers the problem of finding maximum volume (axis-aligned) inscribed boxes in a compact convex set, defined by a finite number of convex inequalities, and presents optimization and geometric approaches for solving them. Several optimization models are developed that can be easily generalized to find other inscribed geometric shapes such as triangles, rhombi, and squares. To find the largest volume axis-aligned inscribed rectangles in the higher dimensions, an interior-point method algorithm is presented and analyzed. For two-dimensional space, a parametrized optimization approach is developed to find the largest area (axis-aligned) inscribed rectangles in convex sets. The optimization approach provides a uniform framework for solving a wide variety of relevant problems. Finally, two computational geometric (1−ε) –approximation algorithms with sublinear running times are presented that improve the previous results. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms—Continuous. Funding: The author is grateful for the support of Northeastern University for this research. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0239) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0239). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

The Power of Traffic Tolls The paper "In Congestion Games, Taxes Achieve Optimal Approximation" by Paccagnan and Gairing investigates the power and limitations of taxes as interventions in congestion games. Perhaps surprisingly, they find that efficiently computed taxes can achieve the same performance as the best polynomial time algorithm, even when the algorithm has full control over the agents' actions. The authors establish three main results to support this claim. First, they prove that minimizing congestion is NP-hard to approximate within a given factor based on the latency functions. Second, they demonstrate how convex optimization tools can be used to design optimal taxes. Third, they provide a polynomial time algorithm with an approximation factor matching the hardness barrier. The upshot of their contribution can be summarized as follows: Judiciously designed taxes achieve optimal approximation, and no other tractable intervention can improve upon this result. In this work, we address the problem of minimizing social cost in atomic congestion games. For this problem, we present lower bounds on the approximation ratio achievable in polynomial time and demonstrate that efficiently computable taxes result in polynomial time algorithms matching such bounds. Perhaps surprisingly, these results show that indirect interventions, in the form of efficiently computed taxation mechanisms, yield the same performance achievable by the best polynomial time algorithm, even when the latter has full control over the agents' actions. It follows that no other tractable approach geared at incentivizing desirable system behavior can improve upon this result, regardless of whether it is based on taxations, coordination mechanisms, information provision, or any other principle. In short: Judiciously chosen taxes achieve optimal approximation. Three technical contributions underpin this conclusion. First, we show that computing the minimum social cost is NP -hard to approximate within a given factor depending solely on the admissible cost functions. Second, we design a polynomially computable taxation mechanism whose efficiency (price of anarchy) matches this hardness factor, and thus is optimal among all tractable mechanisms. As these results extend to coarse correlated equilibria, any no-regret algorithm inherits the same performances, allowing us to devise polynomial time algorithms with optimal approximation. Supplemental Material: The e-companion is available at https://doi.org/10.1287/opre.2021.0526. [ABSTRACT FROM AUTHOR]

We study a shipment consolidation problem commonly faced by companies that outsource logistics operations and operate in a commit-to-delivery mode. It involves delivering a given set of orders to their destinations by their committed due times using multiple shipping methods at the minimum total shipping and inventory cost. The shipping cost is generally nonlinear in shipping quantity and can be represented by a subadditive piecewise linear function. We investigate two shipping scenarios, one involving long-haul shipping only and the other involving joint long-haul and short-haul shipping. We develop analytical results and solution algorithms for the shipment consolidation problem under each shipping scenario. The problem under the first shipping scenario is shown to be strongly NP -hard. We find that a simple policy, called the First-Due-First-Delivered (FDFD) policy, which assigns orders with earlier delivery due times to shipping methods with earlier destination arrival times, is very effective. This policy enables us to develop a polynomial time algorithm, which not only solves the problem under the concave shipping cost structure optimally but also achieves a performance guarantee of 2 for the problem under the general subadditive shipping cost structure. For the problem under the second shipping scenario, we extend the FDFD policy for long-haul shipping and derive another policy, called the No-Wait policy, for short-haul shipping. We use these policies to develop a polynomial time algorithm and analyze its performance guarantee. Our computational experiments show that the algorithm significantly outperforms a commercial optimization solver, and its performance is robust across different parameter settings that reflect various practical situations. This paper was accepted by Jeannette Song, operations management. Supplemental Material: The data and e-companion are available at https://doi.org/10.1287/mnsc.2023.4835. [ABSTRACT FROM AUTHOR]

Problem definition: Content promotion policies are crucial for online content platforms to improve content consumption and user engagement. However, traditional promotion policies generally neglect the diffusion effect within a crowd of users. In this paper, we study the candidate generation and promotion optimization (CGPO) problem for an online content platform, emphasizing the incorporation of the diffusion effect. Methodology/results: We propose a diffusion model that incorporates platform promotion decisions to characterize the adoption process of online content. Based on this diffusion model, we formulate the CGPO problem as a mixed-integer program with nonconvex and nonlinear constraints, which is proved to be NP-hard. Additionally, we investigate methods for estimating the diffusion model parameters using available online platform data and introduce novel double ordinary least squares (D-OLS) estimators. We prove the submodularity of the objective function for the CGPO problem, which enables us to find an efficient (1−1/e) -approximation greedy solution. Furthermore, we demonstrate that the D-OLS estimators are consistent and have smaller asymptotic variances than traditional ordinary least squares estimators. By utilizing real data from a large-scale video-sharing platform, we show that our diffusion model effectively characterizes the adoption process of online content. Compared with the policy implemented on the platform, our proposed promotion policy increases total adoptions by 49.90%. Managerial implications: Our research highlights the essential role of diffusion in online content and provides actionable insights for online content platforms to optimize their content promotion policies by leveraging our diffusion model. Funding: R. Zhang is grateful for the financial support from the Hong Kong Research Grants Council General Research Fund [Grants 14502722 and 14504123] and the National Natural Science Foundation of China [Grant 72293560/72293565]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2022.0172. [ABSTRACT FROM AUTHOR]

Problem definition: We investigate the effects of waiting time, mainly due to production in a make-to-batch-order (MTBO) system, on consumer choice behavior, pricing, assortment, and model estimation. In an MTBO system, the seller/manufacturer first collects orders placed within a certain period of time into a batch and then starts the production process. After the production of all orders in a batch are complete, the products are then shipped and delivered to individual consumers. Because of batch production and shipping, the disutility of the waiting time exhibits negative externality. Methodology/results: We adopt the widely used multinomial logit (MNL) model as a starting point and incorporate the anticipated wait into consumers' decision making. The derived model, referred to as the MNL with wait model, is a solution of the rational expectation equilibrium and is capable of capturing the effects of negative externality induced by anticipated wait that may change the substitution patterns dramatically. We characterize the multiproduct price optimization problem under the MNL with wait model by establishing a one-to-one mapping between the price vector and the choice probability vector. We find that firms tend to charge higher prices for time-consuming items and charge lower prices for time-saving items compared with the optimal prices under the standard MNL model. In addition to price competition, we also study the Cournot-type competition, in which the decision is the choice probability for each firm and establish the existence of a Nash equilibrium. For assortment optimization, we identify mild conditions under which the optimality of revenue-ordered assortments still holds. However, the assortment problem under the MNL with wait model is generally NP-hard, so we develop approximation algorithms with performance guarantees and provide an easy-to-compute tight upper bound. Moreover, we develop an efficient maximum likelihood-based algorithm for model calibration and further conduct numerical studies to showcase the importance of incorporating disutility due to wait in estimation, pricing, and assortment planning problems. Managerial implications: The MNL with wait model can increase prediction accuracy for consumers' choice behavior especially when they are aware of the potential wait. Failure to take into account the effects of anticipated wait in firms' decision making may lead to substantial losses. Funding: The research of C. Ke is supported in part by the National Natural Science Foundation of China [Grant 72101113]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2020.0346. [ABSTRACT FROM AUTHOR]

We study linear Fisher markets with satiation. In these markets, sellers have earning limits, and buyers have utility limits. Beyond applications in economics, they arise in the context of maximizing Nash social welfare when allocating indivisible items to agents. In contrast to markets with either earning or utility limits, markets with both limits have not been studied before. They turn out to have fundamentally different properties. In general, the existence of competitive equilibria is not guaranteed. We identify a natural property of markets (termed money clearing) that implies existence. We show that the set of equilibria is not always convex, answering a question posed in the literature. We design an FPTAS to compute an approximate equilibrium and prove that the problem of computing an exact equilibrium lies in the complexity class continuous local search (CLS ; i.e., the intersection of polynomial local search (PLS) and polynomial parity arguments on directed graphs (PPAD)). For a constant number of buyers or goods, we give a polynomial-time algorithm to compute an exact equilibrium. We show how (approximate) equilibria can be rounded and provide the first constant-factor approximation algorithm (with a factor of 2.404) for maximizing Nash social welfare when agents have capped linear (also known as budget-additive) valuations. Finally, we significantly improve the approximation hardness for additive valuations to 8/7>1.069. Funding: J. Garg was supported by the National Science Foundation [Grant CCF-1942321 (CAREER)]. M. Hoefer was supported by Deutsche Forschungsgemeinschaft [Grants Ho 3831/5-1, Ho 3831/6-1, and Ho 3831/7-1]. [ABSTRACT FROM AUTHOR]

Theoretical studies on evolutionary algorithms have developed vigorously in recent years. Many such algorithms have theoretical guarantees in both running time and approximation ratio. Some approximation mechanism seems to be inherently embedded in many evolutionary algorithms. In this paper, we identify such a relation by proposing a unified analysis framework for a global simple multiobjective evolutionary algorithm (GSEMO) and apply it on a minimum weight general cover problem, which is general enough to subsume many important problems including the minimum submodular cover problem in which the submodular function is real-valued, and the minimum connected dominating set problem for which the potential function is nonsubmodular. We show that GSEMO yields theoretically guaranteed approximation ratios matching those achievable by a greedy algorithm in expected polynomial time when the potential function g is polynomial in the input size and the minimum gap between different g-values is a constant. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported by National Natural Science Foundation of China [11771013, U20A2068]; Zhejiang Provincial Natural Science Foundation of China [LD19A010001]. [ABSTRACT FROM AUTHOR]

In this paper, we study the classic submodular maximization problem subject to a group equality constraint under both nonadaptive and adaptive settings. It is shown that the utility function of many machine learning applications, including data summarization, influence maximization in social networks, and personalized recommendation, satisfies the property of submodularity. Hence, maximizing a submodular function subject to various constraints can be found at the heart of many of those applications. On a high level, submodular maximization aims to select a group of most representative items (e.g., data points). However, the design of most existing algorithms does not incorporate the fairness constraint, leading to underrepresentation or overrepresentation of some particular groups. This motivates us to study the submodular maximization problem with group equality, in which we aim to select a group of items to maximize a (possibly nonmonotone) submodular utility function subject to a group equality constraint. To this end, we develop the first constant-factor approximation algorithm for this problem. The design of our algorithm is robust enough to be extended to solving the submodular maximization problem under a more complicated adaptive setting. Moreover, we further extend our study to incorporating a global cardinality constraint and other fairness notations. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Supplemental Material: The online supplement is available at https://doi.org/10.1287/ijoc.2022.0384. [ABSTRACT FROM AUTHOR]

Rank aggregation combines the preference rankings of multiple alternatives from different voters into a single consensus ranking, providing a useful model for a variety of practical applications but posing a computationally challenging problem. In this paper, we provide an effective hybrid evolutionary ranking algorithm to solve the rank aggregation problem with both complete and partial rankings. The algorithm features a semantic crossover based on concordant pairs and an enhanced late acceptance local search method reinforced by a relaxed acceptance and replacement strategy and a fast incremental evaluation mechanism. Experiments are conducted to assess the algorithm, indicating a highly competitive performance on both synthetic and real-world benchmark instances compared with state-of-the-art algorithms. To demonstrate its practical usefulness, the algorithm is applied to label ranking, a well-established machine learning task. We additionally analyze several key algorithmic components to gain insight into their operation. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported by the National Natural Science Foundation of China [Grant 72371157] and Shanghai Pujiang Programme [Grant 23PJC069]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0019) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0019). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

This paper studies a classic maximum entropy sampling problem (MESP), which aims to select the most informative principal submatrix of a prespecified size from a covariance matrix. MESP is widely applied to many areas, including healthcare, power systems, manufacturing, and data science. By investigating its Lagrangian dual and primal characterization, we derive a novel convex integer program for MESP and show that its continuous relaxation yields a near-optimal solution. The results motivate us to study efficient approximation algorithms and develop their approximation bounds for MESP, which improves the best known one in the literature. This paper studies a classic maximum entropy sampling problem (MESP), which aims to select the most informative principal submatrix of a prespecified size from a covariance matrix. By investigating its Lagrangian dual and primal characterization, we derive a novel convex integer program for MESP and show that its continuous relaxation yields a near-optimal solution. The results motivate us to develop a sampling algorithm and derive its approximation bound for MESP, which improves the best known bound in literature. We then provide an efficient deterministic implementation of the sampling algorithm with the same approximation bound. Besides, we investigate the widely used local search algorithm and prove its first known approximation bound for MESP. The proof techniques further inspire for us an efficient implementation of the local search algorithm. Our numerical experiments demonstrate that these approximation algorithms can efficiently solve medium-size and large-scale instances to near optimality. Finally, we extend the analyses to the A-optimal MESP, for which the objective is to minimize the trace of the inverse of the selected principal submatrix. Funding: This work was supported by the National Science Foundation Division of Information and Intelligent Systems [Grant 2246417] and Division of Civil, Mechanical and Manufacturing Innovation [Grant 2246414]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/opre.2023.2488. [ABSTRACT FROM AUTHOR]

We consider single-machine scheduling problems that are natural generalizations or variations of the min-sum set-cover problem. For these scheduling problems, we give new approximation algorithms. Some of these algorithms rely on time-indexed linear programming relaxations. We show how a variant of alpha-point scheduling leads to the best known approximation ratios, including a guarantee of four for an interesting special case of the so-called generalized min-sum set-cover problem. We also make explicit the connection between the greedy algorithm for min-sum set cover and the concept of Sidney decomposition for precedence-constrained single-machine scheduling and show how this leads to a 4-approximation algorithm for single-machine scheduling with so-called bipartite OR-precedence constraints. Funding: This work has been supported by the Alexander von Humboldt Foundation with funds from the German Federal Ministry of Education and Research. [ABSTRACT FROM AUTHOR]

We study the D-optimal Data Fusion (DDF) problem, which aims to select new data points, given an existing Fisher information matrix, so as to maximize the logarithm of the determinant of the overall Fisher information matrix. We show that the DDF problem is NP-hard and has no constant-factor polynomial-time approximation algorithm unless P = NP. Therefore, to solve the DDF problem effectively, we propose two convex integer-programming formulations and investigate their corresponding complementary and Lagrangian-dual problems. Leveraging the concavity of the objective functions in the two proposed convex integer-programming formulations, we design an exact algorithm, aimed at solving the DDF problem to optimality. We further derive a family of submodular valid inequalities and optimality cuts, which can significantly enhance the algorithm performance. We also develop scalable randomized-sampling and local-search algorithms with provable performance guarantees. Finally, we test our algorithms using real-world data on the new phasor-measurement-units placement problem for modern power grids, considering the existing conventional sensors. Our numerical study demonstrates the efficiency of our exact algorithm and the scalability and high-quality outputs of our approximation algorithms. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: Y. Li and W. Xie were supported in part by Division of Civil, Mechanical and Manufacturing Innovation [Grant 2046414] and Division of Computing and Communication Foundations [Grant 2246417]. J. Lee was supported in part by Air Force Office of Scientific Research [Grants FA9550-19-1-0175 and FA9550-22-1-0172]. M. Fampa was supported in part by Conselho Nacional de Desenvolvimento Científico e Tecnológico [Grants 305444/2019-0 and 434683/2018-3]. F. Qiu and R. Yao were supported in part by the U.S. Department of Energy Advanced Grid Modeling Program under [Grant DE-OE0000875]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2022.0235. [ABSTRACT FROM AUTHOR]

This study considers a well-known critical node detection problem that aims to minimize a pairwise connectivity measure of an undirected graph via the removal of a subset of nodes (referred to as critical nodes) subject to a cardinality constraint. Potential applications include epidemic control, emergency response, vulnerability assessment, carbon emission monitoring, network security, and drug design. To solve the problem, we present a "reduce-solve-combine" memetic search approach that integrates a problem reduction mechanism into the popular population-based memetic algorithm framework. At each generation, a common pattern mined from two parent solutions is first used to reduce the given problem instance, then the reduced instance is solved by a component-based hybrid neighborhood search that effectively combines an articulation point impact strategy and a node weighting strategy, and finally an offspring solution is produced by combining the mined common pattern and the solution of the reduced instance. Extensive evaluations on 42 real-world and synthetic benchmark instances show the efficacy of the proposed method, which discovers nine new upper bounds and significantly outperforms the current state-of-the-art algorithms. Investigation of key algorithmic modules additionally discloses the importance of the proposed ideas and strategies. Finally, we demonstrate the generality of the proposed method via its adaptation to solve the node-weighted critical node problem. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported by the National Natural Science Foundation of China [Grants 72371157, 61903144, 72031007]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0130) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0130). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

In "Sequential Competitive Facility Location: Exact and Approximate Algorithms," Qi et al. consider a competitive facility location problem (CFLP), where two firms sequentially open new facilities within their budgets and maximize their market shares of demand following a probabilistic choice model. They derive an equivalent, single-level mixed-integer nonlinear program (MINLP) reformulation of the bilevel MINLP and exploit the problem structures to derive valid inequalities based on submodularity and concave overestimation. They also develop an approximation algorithm with a constant approximation guarantee. They further study several extensions of CFLP that have general facility-opening costs, outside competitors, and diverse facility-planning decisions. Their approaches significantly accelerate the computation of CFLP on large-sized instances that have not been solved optimally or even heuristically by existing methods. We study a competitive facility location problem (CFLP), where two firms sequentially open new facilities within their budgets, in order to maximize their market shares of demand that follows a probabilistic choice model. This process is a Stackelberg game and admits a bilevel mixed-integer nonlinear program (MINLP) formulation. We derive an equivalent, single-level MINLP reformulation and exploit the problem structures to derive two valid inequalities based on submodularity and concave overestimation, respectively. We use the two valid inequalities in a branch-and-cut algorithm to find globally optimal solutions. Then, we propose an approximation algorithm to find good-quality solutions with a constant approximation guarantee. We develop several extensions by considering general facility-opening costs and outside competitors as well as diverse facility-planning decisions, and we discuss solution approaches for each extension. We conduct numerical studies to demonstrate that the exact algorithm significantly accelerates the computation of CFLP on large-sized instances that have not been solved optimally or even heuristically by existing methods, and the approximation algorithm can quickly find high-quality solutions. We derive managerial insights based on sensitivity analysis of different settings that affect customers' probabilistic choices and the ensuing demand. Funding: M. Qi was partially supported by the National Natural Science Foundation of China [Grant 71772100] to work on this project. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2022.2339. [ABSTRACT FROM AUTHOR]

Problem definition: Assortment selection is one of the most important decisions faced by retailers. Most existing papers in the literature assume that customers select at most one item out of the offered assortment. Although this is valid in some cases, it contradicts practical observations in many shopping experiences, both in online and brick-and-mortar retail, where customers may buy a basket of products instead of a single item. In this paper, we incorporate customers' multi-item purchase behavior into the assortment optimization problem. We consider both the uncapacitated and capacitated assortment problems under the so-called Multivariate MNL (MVMNL) model, which is one of the most popular multivariate choice models used in the marketing and empirical literature. Methodology/results: We first show that the traditional revenue-ordered assortment may not be optimal. Nonetheless, we show that under some mild conditions, a certain variant of this property holds (in the uncapacitated assortment problem) under the MVMNL model; that is, the optimal assortment consists of revenue-ordered local assortments in each product category. Finding the optimal assortment even when there is no interaction among product categories is still computationally expensive because the revenue thresholds for different categories cannot be computed separately. To tackle the computational complexity, we develop FPTAS for several variants of (capacitated and uncapacitated) assortment problems under MVMNL. Managerial implications: Our analysis reveals that disregarding customers' multi-item purchase behavior in assortment decisions can indeed have a significant negative impact on profitability, demonstrating its practical importance in retail. We numerically show that our proposed algorithm can improve a retailer's expected total revenues (compared with a benchmark policy that does not properly take into account the impact of customers' multi-item choice behavior in assortment decision) by up to 14%. Supplemental Material: The e-companion is available at https://doi.org/10.1287/msom.2021.0526. [ABSTRACT FROM AUTHOR]

Alaei et al. consider the problem of a streaming platform that offers different set of contents with different subscription fees with the goal of maximizing revenue. They characterize the necessary and sufficient condition for the consumer preferences under which a single-tier subscription is optimal. In particular, they show the preferences of the consumers for different contents must be aligned for a single-tier subscription to be optimal. This condition is often violated in practice, establishing the suboptimality of a single-tier offering. They further show that a subscription fee proportional to the number of contents is near-optimal. We consider a media service provider that gives users access to digital goods through subscription. In our model, different types of users with heterogeneous usage rates repeatedly use a platform over a period of time. There are multiple item types on the platform, and the value of an item to a user is random and depends on both the user type and the item type. The design of the platform's subscription planning comprises selecting a subscription fee for each set of item types. Before the beginning of the subscription period, given the subscription planning, users decide which set of item types to subscribe to (if any). During the subscription period, a user pays zero price to use an item if it has subscribed to a set that includes it and pays its rental price otherwise. For an exogenously given rental price, we establish the sufficient and necessary condition for the optimality of grand subscription—offering a single subscription set that includes all items. We then consider a setting in which the platform chooses both the subscription fee for each set of item types and the rental price of each item type and establish that there exist subscription fees proportional to the cardinality of each set of item types (with no rental offers) that achieve a logarithmic approximation (in the number of item types) of the optimal revenue. Finally, we demonstrate that our performance guarantee is tight for a class of problem instances. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2023.2468. [ABSTRACT FROM AUTHOR]

There is an error in our paper [Paul A, Freund D, Ferber A, Shmoys DB, Williamson DP (2020) Budgeted prize-collecting traveling salesman and minimum spanning tree problems. Math. Oper. Res. 45(2):576–590]. In that paper, we consider constrained versions of the prize-collecting traveling salesman and the prize-collecting minimum spanning tree problems. The goal is to maximize the number of vertices in the returned tour/tree subject to a bound on the tour/tree cost. Rooted variants of the problems have the additional constraint that a given vertex, the root, must be contained in the tour/tree. In our previous paper, we present a 2-approximation algorithm for the rooted and unrooted versions of both the tree and tour variants using a parameterized primal–dual approach. Here, we illustrate an error in the proof of a lemma for the rooted version of the algorithm and show that the algorithm has no finite approximation guarantee for the rooted version of the problem. We also show that the lemma and the approximation guarantee of 2 continue to hold true for the unrooted version. This leaves the best-known approximations for the rooted tour an established (2 + ϵ) -approximation algorithm and for the tree variant a previously published poly-log approximation algorithm. [ABSTRACT FROM AUTHOR]

We study the capacity planning and allocation decisions for multiple heterogeneous resources, considering potential demand scenarios, where each demand requests a subset of the available resource types simultaneously at a specified time, location, and duration (smRmD). We model this problem as a two-stage stochastic integer program and consider two variants for the objective function: (a) maximize the expected reward of demands met over all scenarios, subject to a budget B for resources, and (b) maximize the expected reward of demands met over all scenarios minus the cost of resources. Contributions of this work include (i) a thorough complexity analysis of smRmD and its variants, (ii) analysis of structural properties, (iii) development of various approximation algorithms using the unique structural properties of smRmD and its variants, and (iv) an extensive computational study to explore the ease with which exact and approximate solutions may be found. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This research has been supported in part by National Science Foundation (NSF) Graduate Research Fellowship [DGE-1650044], NSF [Grants CMMI-1538860, NSF-AF:1910423, and NSF-AF:1717947], and the following Georgia Tech benefactors: William W. George, Andrea Laliberte, Richard "Rick" E. & Charlene Zalesky, and Claudia & Paul Raines. [ABSTRACT FROM AUTHOR]

A multidepot capacitated vehicle routing problem aims to serve customers' demands using a fleet of capacitated vehicles located in multiple depots, such that the total travel cost of the vehicles is minimized. We study a variant of this problem, the k-depot split delivery vehicle routing problem (or k-DSDVRP in short), for the situation where each customer's demand can be served by more than one vehicle, and the total number of depots, denoted by k ≥ 2 , is a fixed constant. This is a challenging problem with broad applications in the logistics industry, for which no constant ratio approximation algorithm is known. We develop a new approximation algorithm for the k-DSDVRP, ensuring an approximation ratio of (6 − 4 / k) and a polynomial running time for any fixed constant k ≥ 2. To achieve this, we propose a novel solution framework based on a new relaxation of the problem, a cycle splitting procedure, and a vehicle assignment procedure. To further enhance its efficiency for practical usage, we adapt the newly developed approximation algorithm to a heuristic, which runs in polynomial time even when k is arbitrarily large. Experimental results show that this heuristic outperforms a commercial optimization solver and a standard vehicle routing heuristic. Moreover, our newly proposed solution framework can be applied to developing new constant ratio approximation algorithms for several other variants of the k-DSDVRP with k ≥ 2 being a fixed constant. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported in part by the National Natural Science Foundation of China [Grants 71971177, 71725001, U1811462], Research Grants Council of Hong Kong SAR, China [Grant 15221619], and Guangdong Basic and Applied Basic Research Foundation [Grant 2023A1515030260]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2021.0193. The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2021.0193) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2021.0193). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

Cybersecurity planning supports the selection of and implementation of security controls in resource-constrained settings to manage risk. Doing so requires considering adaptive adversaries with different levels of strategic sophistication in modeling efforts to support risk management. However, most models in the literature only consider rational or nonstrategic adversaries. Therefore, we study how to inform defensive decision making to mitigate the risk from boundedly rational players, with a particular focus on making integrated, interdependent planning decisions. To achieve this goal, we introduce a modeling framework for selecting a portfolio of security mitigations that interdict adversarial attack plans that uses a structured approach for risk analysis. Our approach adapts adversarial risk analysis and cognitive hierarchy theory to consider a maximum-reliability path interdiction problem with a single defender and multiple attackers who have different goals and levels of strategic sophistication. Instead of enumerating all possible attacks and defenses, we introduce a solution technique based on integer programming and approximation algorithms to iteratively solve the defender's and attackers' problems. A case study illustrates the proposed models and provides insights into defensive planning. Funding: A. Peper and L. A. Albert were supported in part by the National Science Foundation [Grant 2000986]. [ABSTRACT FROM AUTHOR]

This paper studies the distributionally robust fair transit resource allocation model (DrFRAM) under the Wasserstein ambiguity set to optimize the public transit resource allocation during a pandemic. We show that the proposed DrFRAM is highly nonconvex and nonlinear, and it is NP-hard in general. Fortunately, we show that DrFRAM can be reformulated as a mixed integer linear programming (MILP) by leveraging the equivalent representation of distributionally robust optimization and monotonicity properties, binarizing integer variables, and linearizing nonconvex terms. To improve the proposed MILP formulation, we derive stronger ones and develop valid inequalities by exploiting the model structures. Additionally, we develop scenario decomposition methods using different MILP formulations to solve the scenario subproblems and introduce a simple yet effective no one left-based approximation algorithm with a provable approximation guarantee to solve the model to near optimality. Finally, we numerically demonstrate the effectiveness of the proposed approaches and apply them to real-world data provided by the Blacksburg Transit. History: This paper has been accepted for the Transportation Science Special Issue on Emerging Topics in Transportation Science and Logistics. Funding: This work was supported by the Division of Computing and Communication Foundations [Grant 2153607] and the Division of Civil, Mechanical and Manufacturing Innovation [Grant 2046426]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2022.1159. [ABSTRACT FROM AUTHOR]

Ride-pooling, which accommodates multiple passenger requests in a single trip, has the potential to substantially enhance the throughput of mobility-on-demand (MoD) systems. This paper investigates MoD systems that operate mixed fleets composed of "basic supply" and "augmented supply" vehicles. When the basic supply is insufficient to satisfy demand, augmented supply vehicles can be repositioned to serve rides at a higher operational cost. We formulate the joint vehicle repositioning and ride-pooling assignment problem as a two-stage stochastic integer program, where repositioning augmented supply vehicles precedes the realization of ride requests. Sequential ride-pooling assignments aim to maximize total utility or profit on a shareability graph: a hypergraph representing the matching compatibility between available vehicles and pending requests. Two approximation algorithms for midcapacity and high-capacity vehicles are proposed in this paper; the respective approximation ratios are 1 / p 2 and (e − 1) / (2 e + o (1)) p ln p , where p is the maximum vehicle capacity plus one. Our study evaluates the performance of these approximation algorithms using an MoD simulator, demonstrating that these algorithms can parallelize computations and achieve solutions with small optimality gaps (typically within 1%). These efficient algorithms pave the way for various multimodal and multiclass MoD applications. History: This paper has been accepted for the Transportation Science Special Issue on Emerging Topics in Transportation Science and Logistics. Funding: This work was supported by the National Science Foundation [Grants CCF-2006778 and FW-HTF-P 2222806], the Ford Motor Company, and the Division of Civil, Mechanical, and Manufacturing Innovation [Grants CMMI-1854684, CMMI-1904575, and CMMI-1940766]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2021.0349. [ABSTRACT FROM AUTHOR]

This paper presents an effective perturbation-based thresholding search for two popular and challenging packing problems with minimal containers: packing N identical circles in a square and packing N identical spheres in a cube. Following the penalty function approach, we handle these constrained optimization problems by solving a series of unconstrained optimization subproblems with fixed containers. The proposed algorithm relies on a two-phase search strategy that combines a thresholding search method reinforced by two general-purpose perturbation operators and a container adjustment method. The performance of the algorithm is assessed relative to a large number of benchmark instances widely studied in the literature. Computational results show a high performance of the algorithm on both problems compared with the state-of-the-art results. For circle packing, the algorithm improves 156 best-known results (new upper bounds) in the range of 2 ≤ N ≤ 400 and matches 242 other best-known results. For sphere packing, the algorithm improves 66 best-known results in the range of 2 ≤ N ≤ 200 , whereas matching the best-known results for 124 other instances. Experimental analyses are conducted to shed light on the main search ingredients of the proposed algorithm consisting of the two-phase search strategy, the mixed perturbation and the parameters. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported by the National Natural Science Foundation of China [Grants 61703213 and 61933005]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.1290) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0004) at (http://dx.doi.org/10.5281/zenodo.7579558). [ABSTRACT FROM AUTHOR]

We study the dynamic assortment planning problem under the widely utilized multinomial logit choice model (MNL). In this single-period assortment optimization and inventory management problem, the retailer jointly decides on an assortment, that is, a subset of products to be offered, as well as on the inventory levels of these products, aiming to maximize the expected revenue subject to a capacity constraint on the total number of units stocked. The demand process is formed by a stochastic stream of arriving customers, who dynamically substitute between products according to the MNL model. Although this dynamic setting is extensively studied, the best known approximation algorithm guarantees an expected revenue of at least 0.139 times the optimum, assuming that the demand distribution has an increasing failure rate. In this paper, we establish novel stochastic inequalities showing that, for any given inventory levels, the expected demand of each offered product is "stable" under basic algorithmic operations, such as scaling the MNL preference weights and shifting inventory across comparable products. We exploit this sensitivity analysis to devise the first approximation scheme for dynamic assortment planning under the MNL model, allowing one to efficiently compute inventory levels that approach the optimal expected revenue within any degree of accuracy. The running time of this algorithm is polynomial in all instance parameters except for an exponential dependency on logΔ, where Δ = wmax/wmin stands for the ratio of the extremal MNL preference weights. Finally, we conduct simulations on simple synthetic instances with uniform preference weights (i.e., Δ = 1). Using our approximation scheme to derive tight upper bounds, we gain some insights into the performance of several heuristics proposed by previous literature. [ABSTRACT FROM AUTHOR]

We study the incremental knapsack problem, where one wishes to sequentially pack items into a knapsack whose capacity expands over a finite planning horizon, with the objective of maximizing time-averaged profits. Although various approximation algorithms were developed under mitigating structural assumptions, obtaining nontrivial performance guarantees for this problemin its utmost generality has remained an open question thus far. In this paper, we devise a polynomial-time approximation scheme for general instances of the incremental knapsack problem, which is the strongest guarantee possible given existing hardness results. In contrast to earlier work, our algorithmic approach exploits an approximate dynamic programming formulation. Starting with a simple exponentially sized dynamic program, we prove that an appropriate composition of state pruning ideas yields a polynomially sized state space with negligible loss of optimality. The analysis of this formulation synthesizes various techniques, including new problem decompositions, parsimonious counting arguments, and efficient roundingmethods, thatmay be of broader interest. [ABSTRACT FROM AUTHOR]

We consider a joint assortment optimization and customization problem under a mixture of multinomial logit models. In this problem, a firm faces customers of different types, each making a choice within an offered assortment according to the multinomial logit model with different parameters. The problem takes place in two stages. In the first stage, the firm picks an assortment of products to carry the subject to a cardinality constraint. In the second stage, a customer of a certain type arrives into the system. Observing the type of the customer, the firm customizes the assortment that it carries by, possibly, dropping products from the assortment. The goal of the firm is to find an assortment of products to carry and a customized assortment to offer to each customer type that can arrive in the second stage to maximize the expected revenue from a customer visit. The problem arises, for example, in online platforms, where retailers commit to a selection of products before the start of the selling season; but they can potentially customize the displayed assortment for each customer type. We refer to this problem as the Customized Assortment Problem (CAP). Letting m be the number of customer types, we show that the optimal expected revenue of (CAP) can beO(m) times greater than the optimal expected revenue of the corresponding model without customization and this bound is tight. We establish that (CAP) is NP-hard to approximatewithin a factor better than 1- 1=e, so we focus on providing an approximation framework for (CAP). As our main technical contribution, we design a novel algorithm, which we refer to as Augmented Greedy; building on it, we give a O(1=logm)-approximation algorithm to (CAP). Also, we present a fully polynomial-time approximation scheme for (CAP) when the number of customer types is constant. Considering the case where we have a cardinally constraint on the assortment offered to each customer type in the second stage of (CAP), we give a O(1= ... m log m)-approximation algorithm. In our computational experiments, we demonstrate the value of customization by using a data set from Expedia and check the practical performance of our approximation algorithm. [ABSTRACT FROM AUTHOR]

Logistics service providers use transportation assets to offer services to their customers. To cope with demand variability, they may acquire additional assets on a one-off (spot) basis. The planner's problem is to determine the optimal level of assets acquired upfront, such that their cost is minimized, for a given planning horizon. Our formulation captures a nontrivial complication: Although ordering quantities are pertinent to asset acquisition, customer demand is in the form of service requests. Not only does each request have a stochastic duration, but also the total number of requests per customer is uncertain. We introduce a two-stage newsvendor model where demand for spot assets is derived through optimal cutting-stock patterns. Leveraging results from bin-packing, we propose polynomial algorithms that have worst-case guarantees for upper and lower bounds. Our method finds optimal solutions to instances intractable by commercial solvers. We investigate demand variability by means of a factorial experiment. We find that, whereas variability in the number of requests leads to higher costs, variability in each request's duration can reduce costs. Finally, we demonstrate the modularity of our approach with two extensions: asset routing and outsourcing. Our results provide a practical approach to transportation asset acquisition and offer insights on the differing impact of demand uncertainty on the total acquisition cost. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2023.1201. [ABSTRACT FROM AUTHOR]

Decomposition techniques are an important component of modern heuristics for large instances of vehicle routing problems. The current literature lacks a characterization of decomposition strategies and a systematic investigation of their impact when integrated into state-of-the-art heuristics. This paper fills this gap: We discuss the main characteristics of decomposition techniques in vehicle routing heuristics, highlight their strengths and weaknesses, and derive a set of desirable properties. Through an extensive numerical campaign, we investigate the impact of decompositions within two algorithms for the capacitated vehicle routing problem: the Adaptive Large Neighborhood Search of Pisinger and Ropke (2007) and the Hybrid Genetic Search of Vidal et al. (2012). We evaluate the quality of popular decomposition techniques from the literature and propose new strategies. We find that route-based decomposition methods, which define subproblems by means of the customers contained in selected subsets of the routes of a given solution, generally appear superior to path-based methods, which merge groups of customers to obtain smaller subproblems. The newly proposed decomposition barycenter clustering achieves the overall best performance and leads to significant gains compared with using the algorithms without decomposition. History: Erwin Pesch, Area Editor for Heuristic Search and Approximation Algorithms. Funding: This work was supported by the U.S. Air Force [Grant FA9550-17-1-0234], the Ministerio de Ciencia e Innovación (Juan de la Cierva Formación), H2020 Marie Skłodowska-Curie Actions [Grant 945380], the Ministero dell'Università e della Ricerca [Grant 2015JJLC3E_002], the Conselho Nacional de Desenvolvimento Científico e Tecnológico [Grant 308528/2018-2], and the Fundação Carlos Chagas Filho de Amparo à Pesquisa do Estado do Rio de Janeiro [Grant E-26/202.790/2019]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.1288) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0048) at (http://dx.doi.org/10.5281/zenodo.7613129). [ABSTRACT FROM AUTHOR]

Problem definition: We consider a revenue management problem that arises from the selling of high-speed train tickets in China. Compared with traditional network revenue management problems, the new feature of our problem is the assign-to-seat restriction. That is, each request, if accepted, must be assigned instantly to a single seat throughout the whole journey, and later adjustment is not allowed. When making decisions, the seller needs to track not only the total seat capacity available, but also the status of each seat. Methodology/results: We build a modified network revenue management model for this problem. First, we study a static problem in which all requests are given. Although the problem is NP-hard in general, we identify conditions for solvability in polynomial time and propose efficient approximation algorithms for general cases. We then introduce a bid-price control policy based on a novel maximal sequence principle. This policy accommodates nonlinearity in bid prices and, as a result, yields a more accurate approximation of the value function than a traditional bid-price control policy does. Finally, we combine a dynamic view of the maximal sequence with the static solution of a primal problem to propose a "re-solving a dynamic primal" policy that can achieve uniformly bounded revenue loss under mild assumptions. Numerical experiments using both synthetic and real data document the advantage of our proposed policies on resource-allocation efficiency. Managerial implications: The results of this study reveal connections between our problem and traditional network revenue management problems. Particularly, we demonstrate that by adaptively using our proposed methods, the impact of the assign-to-seat restriction becomes limited both in theory and practice. Funding: S. Liu's research is partly supported by the National Natural Science Foundation of China (NSFC) [Grant NSFC-72072117]. Z. Wang's research is partly supported by the NSFC [Grant NSFC-72150002]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2023.1188. [ABSTRACT FROM AUTHOR]

Problem definition: On-demand delivery has become increasingly popular around the world. Motivated by a large grocery chain store who offers fast on-demand delivery services, we model and solve a stochastic dynamic driver dispatching and routing problem for last-mile delivery systems where on-time performance is the main target. The system operator needs to dispatch a set of drivers and specify their delivery routes facing random demand that arrives over a fixed number of periods. The resulting stochastic dynamic program is challenging to solve because of the curse of dimensionality. Methodology/results: We propose a novel structured approximation framework to approximate the value function via a parametrized dispatching and routing policy. We analyze the structural properties of the approximation framework and establish its performance guarantee under large-demand scenarios. We then develop efficient exact algorithms for the approximation problem based on Benders decomposition and column generation, which deliver verifiably optimal solutions within minutes. Managerial implications: The evaluation results on a real-world data set show that our framework outperforms the current policy of the company by 36.53% on average in terms of delivery time. We also perform several policy experiments to understand the value of dynamic dispatching and routing with varying fleet sizes and dispatch frequencies. Funding: This work was supported by the National Natural Science Foundation of China [Grants 72222011 and 72171112], China Association for Science and Technology [Grant 2019QNRC001], and the Natural Sciences and Engineering Research Council of Canada [Grant RGPIN-2022-04950]. Supplemental Material: The online appendices are available at https://doi.org/10.1287/msom.2022.1171. [ABSTRACT FROM AUTHOR]

Problem definition: Retailers have become increasingly interested in personalizing their products and services such as promotions. For this, we need new personalized demand models. Unfortunately, social data are not available to many retailers because of cost and privacy issues. Thus, we focus on the problem of detecting customer relationships from transactional data and using them to target promotions to the right customers. Academic/practical relevance: From an academic point of view, this paper solves the novel problem of jointly detecting customer trends and using them for optimal promotion targeting. Notably, we estimate the causal customer-to-customer trend effect solely from transactional data and target promotions for multiple items and time periods. In practice, we provide a new tool for Oracle Retail clients that personalizes promotions. Methodology: We develop a novel customer trend demand model distinguishing between a base purchase probability, capturing factors such as price and seasonality, and a customer trend probability, capturing customer-to-customer trend effects. The estimation procedure is based on regularized bounded variables least squares and instrumental variable methods. The resulting customer trend estimates feed into the dynamic promotion targeting optimization problem, formulated as a nonlinear mixed-integer optimization model. Though it is nondeterministic polynomial-time hard, we propose a greedy algorithm. Results: We prove that our customer-to-customer trend estimates are statistically consistent and that the greedy optimization algorithm is provably good. Having access to Oracle Retail fashion client data, we show that our demand model reduces the weighted-mean absolute percentage error by 11% on average. Also, we provide evidence of the causality of our estimates. Finally, we demonstrate that the optimal policy increases profits by 3%–11%. Managerial implications: The demand model with customer trend and the optimization model for targeted promotions form a decision-support tool for promotion planning. Next to general planning, it also helps to find important customers and target them to generate additional sales. History: This paper has been accepted as part of the 2019 Manufacturing & Service Operations Management Practice-Based Research Competition. Funding: This work was supported by the U.S. National Science Foundation [Grant CMMI-156334]. Funding from the Oracle Corporation through an ERO grant is also gratefully acknowledged. Supplemental Material: The online appendices are available at https://doi.org/10.1287/msom.2020.0893. [ABSTRACT FROM AUTHOR]

We propose a new data-driven approach for addressing multistage stochastic linear optimization problems with unknown distributions. The approach consists of solving a robust optimization problem that is constructed from sample paths of the underlying stochastic process. We provide asymptotic bounds on the gap between the optimal costs of the robust optimization problem and the underlying stochastic problem as more sample paths are obtained, and we characterize cases in which this gap is equal to zero. To the best of our knowledge, this is the first sample path approach for multistage stochastic linear optimization that offers asymptotic optimality guarantees when uncertainty is arbitrarily correlated across time. Finally, we develop approximation algorithms for the proposed approach by extending techniques from the robust optimization literature and demonstrate their practical value through numerical experiments on stylized data-driven inventory management problems. This paper was accepted by David Simchi-Levi, optimization. Funding: S. Shtern was supported by the Israel Science Foundation [Grant 1460/19]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/mnsc.2022.4352. [ABSTRACT FROM AUTHOR]

The goal of a sequential decision-making problem is to design an interactive policy that adaptively selects a group of items, each selection is based on the feedback from the past, to maximize the expected utility of selected items. It has been shown that the utility functions of many real-world applications are adaptive submodular. However, most of existing studies on adaptive submodular optimization focus on the average-case, that is, their objective is to find a policy that maximizes the expected utility over a known distribution of realizations. Unfortunately, a policy that has a good average-case performance may have very poor performance under the worst-case realization. In this study, we propose to study two variants of adaptive submodular optimization problems, namely, worst-case adaptive submodular maximization and robust submodular maximization. The first problem aims to find a policy that maximizes the worst-case utility and the latter one aims to find a policy, if any, that achieves both near optimal average-case utility and worst-case utility simultaneously. We introduce a new class of stochastic functions, called worst-case submodular function. For the worst-case adaptive submodular maximization problem subject to a p-system constraint, we develop an adaptive worst-case greedy policy that achieves a 1 p + 1 approximation ratio against the optimal worst-case utility if the utility function is worst-case submodular. For the robust adaptive submodular maximization problem subject to cardinality constraints (respectively, partition matroid constraints), if the utility function is both worst-case submodular and adaptive submodular, we develop a hybrid adaptive policy that achieves an approximation close to 1 − e − 1 2 (respectively, 1/3) under both worst- and average-case settings simultaneously. We also describe several applications of our theoretical results, including pool-base active learning, stochastic submodular set cover, and adaptive viral marketing. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.1239. [ABSTRACT FROM AUTHOR]

We present a gradient-based algorithm for solving a class of simulation optimization problems in which the objective function is the quantile of a simulation output random variable. In contrast with existing quantile (quantile derivative) estimation techniques, which aim to eliminate the estimator bias by gradually increasing the simulation sample size, our algorithm incorporates a novel recursive procedure that only requires a single simulation sample at each step to simultaneously obtain quantile and quantile derivative estimators that are asymptotically unbiased. We show that these estimators, when coupled with the standard gradient descent method, lead to a multitime-scale stochastic approximation type of algorithm that converges to an optimal quantile value with probability one. In our numerical experiments, the proposed algorithm is applied to optimal investment portfolio problems, resulting in new solutions that complement those obtained under the classical Markowitz mean-variance framework. History: Accepted by Alice E. Smith, Editor-in-Chief; Bruno Tuffin, Area Editor for Simulation. Funding: The work of Y. Peng was supported in part by the National Natural Science Foundation of China (NSFC) [Grants 72022001, 92146003, and 71901003], and by the Key Research and Development Programof Beijing Municipal Science and Technology Commission. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2022.1214. [ABSTRACT FROM AUTHOR]

Jobs in modern parallel-computing frameworks, such as Hadoop and Spark, are subject to several constraints. In these frameworks, the data are typically distributed across a cluster of machines and is processed in multiple stages. Therefore, tasks that belong to the same stage (job) have a collective completion time that is determined by the slowest task in the collection. Furthermore, a task's processing time is machine dependent, and each machine is capable of processing multiple tasks at a time subject to its capacity. In "Scheduling Parallel-Task Jobs Subject to Packing and Placement Constraints," by Mehrnoosh Shafiee and Javad Ghaderi, multiple approximation algorithms with theoretical guarantees are provided to solve the problem under preemptive and nonpreemptive scenarios. The numerical results, using a real traffic trace, demonstrate that the algorithms yield significant gains over the prior approaches. Motivated by modern parallel computing applications, we consider the problem of scheduling parallel-task jobs with heterogeneous resource requirements in a cluster of machines. Each job consists of a set of tasks that can be processed in parallel; however, the job is considered completed only when all its tasks finish their processing, which we refer to as the synchronization constraint. Furthermore, assignment of tasks to machines is subject to placement constraints, that is, each task can be processed only on a subset of machines, and processing times can also be machine dependent. Once a task is scheduled on a machine, it requires a certain amount of resource from that machine for the duration of its processing. A machine can process (pack) multiple tasks at the same time; however, the cumulative resource requirement of the tasks should not exceed the machine's capacity. Our objective is to minimize the weighted average of the jobs' completion times. The problem, subject to synchronization, packing, and placement constraints, is NP-hard, and prior theoretical results only concern much simpler models. For the case that migration of tasks among the placement-feasible machines is allowed, we propose a preemptive algorithm with an approximation ratio of (6 + ϵ). In the special case that only one machine can process each task, we design an algorithm with an improved approximation ratio of four. Finally, in the case that migrations (and preemptions) are not allowed, we design an algorithm with an approximation ratio of 24. Our algorithms use a combination of linear program relaxation and greedy packing techniques. We present extensive simulation results, using a real traffic trace, that demonstrate that our algorithms yield significant gains over the prior approaches. Funding: This work was supported by the National Science Foundation [Grants CNS-1652115 and CNS-1717867]. Supplemental Material: The online appendices are available at https://doi.org/10.1287/opre.2021.2198. [ABSTRACT FROM AUTHOR]

Problem definition: We focus on modeling and evaluating an emergency service system in which cross-trained fire-medics are pooled and respond to both fire calls and medical emergencies. Academic/practical relevance: Fire demand in the United States has decreased dramatically in the last nearly four decades, whereas emergency medical calls have surged. With this changing landscape, cities are under pressure to reduce their budgets by closing fire stations. We evaluate the alternative of implementing a fire-medic system in terms of cost savings and response time performance. Methodology: A cross-trained fire-medic unit may be in one of three states: available, busy at an emergency medical incident, or busy at a fire call. An exact model for the fire-medic system has exponential complexity. We develop a fast approximation algorithm that has linear complexity and can be used to solve three-state problems of any size. Results: Our approximation algorithm yields accurate predictions of response times and unit workloads and provides rapid solution times. We apply our model to the fire-medic system in St. Paul, MN, and find close agreement between predicted and actual average response times. A traditional system would require 33% more personnel to achieve about the same average response times. In sensitivity analyses, we show that the fire-medic system outperforms a traditional system over a wide range of values for call rates and number of joint units. Managerial implications: The fire-medic system in St. Paul, MN, saves more than three million dollars annually. The greatest benefit of the fire-medic system is in reducing response times to medical emergencies. We also show that in a fire-medic system that includes separate engine units, it is advantageous to convert the separate engines to fire-medic units. Our fast approximation algorithm can be applied even in the largest cities that implement fire-medic systems to improve resource deployment and reduce costs. Funding: This work was supported by the Shanghai Science and Technology Development Foundation [Grant 21YF1420200]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/msom.2022.1140. [ABSTRACT FROM AUTHOR]

We introduce the pipeline intervention problem, defined by a layered directed acyclic graph and a set of stochastic matrices governing transitions between successive layers. The graph is a stylized model for how people from different populations are presented opportunities, eventually leading to some reward. In our model, individuals are born into an initial position (i.e., some node in the first layer of the graph) according to a fixed probability distribution and then stochastically progress through the graph according to the transition matrices until they reach a node in the final layer of the graph; each node in the final layer has a reward associated with it. The pipeline intervention problem asks how to best make costly changes to the transition matrices governing people's stochastic transitions through the graph subject to a budget constraint. We consider two objectives: social welfare maximization and a fairness-motivated maximin objective that seeks to maximize the value to the population (starting node) with the least expected value. We consider two variants of the maximin objective that turn out to be distinct, depending on whether we demand a deterministic solution or allow randomization. For each objective, we give an efficient approximation algorithm (an additive fully polynomial-time approximation scheme) for constant-width networks. We also tightly characterize the "price of fairness" in our setting: the ratio between the highest achievable social welfare and the social welfare consistent with a maximin optimal solution. Finally, we show that, for polynomial-width networks, even approximating the maximin objective to any constant factor is NP hard even for networks with constant depth. This shows that the restriction on the width in our positive results is essential. [ABSTRACT FROM AUTHOR]

Motivated by bursty bandwidth allocation and by the allocation of virtual machines to servers in the cloud, we consider the online problem of packing items with random sizes into unit-capacity bins. Items arrive sequentially, but on arrival, an item's actual size is unknown; only its probabilistic information is available to the decision maker. Without knowing this size, the decision maker must irrevocably pack the item into an available bin or place it in a new bin. Once packed in a bin, the decision maker observes the item's actual size, and overflowing the bin is a possibility. An overflow incurs a large penalty cost, and the corresponding bin is unusable for the rest of the process. In practical terms, this overflow models delayed services, failure of servers, and/or loss of end-user goodwill. The objective is to minimize the total expected cost given by the sum of the number of opened bins and the overflow penalty cost. We present an online algorithm with expected cost at most a constant factor times the cost incurred by the optimal packing policy when item sizes are drawn from an independent and identically distributed (i.i.d.) sequence of unknown length. We give a similar result when item size distributions are exponential with arbitrary rates. We also study the offline model, where distributions are known in advance but must be packed sequentially. We construct a soft-capacity polynomial-time approximation scheme for this problem and show that the complexity of computing the optimal offline cost is # P -hard. Finally, we provide an empirical study of our online algorithm's performance. [ABSTRACT FROM AUTHOR]

We study the problem of maximizing a nonmonotone submodular function subject to a cardinality constraint in the streaming model. Our main contribution is a single-pass (semi) streaming algorithm that uses roughly O (k / ε 2) memory, where k is the size constraint. At the end of the stream, our algorithm postprocesses its data structure using any off-line algorithm for submodular maximization and obtains a solution whose approximation guarantee is α / (1 + α) − ε , where α is the approximation of the off-line algorithm. If we use an exact (exponential time) postprocessing algorithm, this leads to 1 / 2 − ε approximation (which is nearly optimal). If we postprocess with the state-of-the-art offline approximation algorithm, whose guarantee is α = 0.385 , we obtain a 0.2779-approximation in polynomial time, improving over the previously best polynomial-time approximation of 0.1715. It is also worth mentioning that our algorithm is combinatorial and deterministic, which is rare for an algorithm for nonmonotone submodular maximization, and enjoys a fast update time of O ( ε −2 (log k + log (1 + α))) per element. [ABSTRACT FROM AUTHOR]

We consider the problem of allocating multiple heterogeneous resources geographically and over time to meet demands that require some subset of the available resource types simultaneously at a specified time, location, and duration. The objective is to maximize the total reward accrued from meeting (a subset of) demands. We model this problem as an integer program, show that it is NP-hard, and analyze the complexity of various special cases. We introduce approximation algorithms and an extension to our problem that considers travel costs. Finally, we test the performance of the integer programming model in an extensive computational study. [ABSTRACT FROM AUTHOR]

An Exponentially Faster Algorithm for Submodular Maximization Under a Matroid Constraint This paper studies the problem of submodular maximization under a matroid constraint. It is known since the 1970s that the greedy algorithm obtains a constant-factor approximation guarantee for this problem. Twelve years ago, a breakthrough result by Vondrák obtained the optimal 1 − 1/e approximation. Previous algorithms for this fundamental problem all have linear parallel runtime, which was considered impossible to accelerate until recently. The main contribution of this paper is a novel algorithm that provides an exponential speedup in the parallel runtime of submodular maximization under a matroid constraint, without loss in the approximation guarantee. In this paper, we study submodular maximization under a matroid constraint in the adaptive complexity model. This model was recently introduced in the context of submodular optimization to quantify the information theoretic complexity of black-box optimization in a parallel computation model. Despite the burst in work on submodular maximization in the adaptive complexity model, the fundamental problem of maximizing a monotone submodular function under a matroid constraint has remained elusive. In particular, all known techniques fail for this problem and there are no known constant factor approximation algorithms whose adaptivity is sublinear in the rank of the matroid k or in the worst case sublinear in the size of the ground set n. We present an algorithm that has an approximation guarantee arbitrarily close to the optimal 1 − 1 / e for monotone submodular maximization under a matroid constraint and has near-optimal adaptivity of O (log (n) log (k)). This result is obtained using a novel technique of adaptive sequencing, which departs from previous techniques for submodular maximization in the adaptive complexity model. In addition to our main result, we show how to use this technique to design other approximation algorithms with strong approximation guarantees and polylogarithmic adaptivity. [ABSTRACT FROM AUTHOR]

We study the classic multiperiod joint pricing and inventory control problem in a data-driven setting. In this problem, a retailer makes periodic decisions on the prices and inventory levels of a product that she wishes to sell. The retailer's objective is to maximize the expected profit over a finite horizon by matching the inventory level with a random demand, which depends on the price in each period. In reality, the demand functions or random noise distributions are usually difficult to know exactly, whereas past demand data are relatively easy to collect. We propose a data-driven approximation algorithm that uses precollected demand data to solve the joint pricing and inventory control problem. We assume that the retailer does not know the noise distributions or the true demand functions; instead, we assume either she has access to demand hypothesis sets and the true demand functions can be represented by nonnegative combinations of candidate functions in the demand hypothesis sets, or the true demand function is generalized linear. We prove the algorithm's sample complexity bound: the number of data samples needed in each period to guarantee a near-optimal profit is O (T 6 ϵ − 2 log T) , where T is the number of periods, and ϵ is the absolute difference between the expected profit of the data-driven policy and the expected optimal profit. In a numerical study, we demonstrate the construction of demand hypothesis sets from data and show that the proposed data-driven algorithm solves the dynamic problem effectively and significantly improves the optimality gaps over the baseline algorithms. This paper was accepted by J. George Shanthikumar, big data analytics. [ABSTRACT FROM AUTHOR]

The Bayesian persuasion paradigm of strategic communication models interaction between a privately informed sender and an ignorant but rational receiver. The goal is typically to design a (near-)optimal communication (or signaling) scheme for the sender. It enables the sender to disclose information to the receiver in a way as to incentivize her to take an action that is preferred by the sender. Finding the optimal signaling scheme is known to be computationally difficult in general. This hardness is further exacerbated when the message space is constrained, leading to NP-hardness of approximating the optimal sender utility within any constant factor. In this paper, we show that in several natural and prominent cases the optimization problem is tractable even when the message space is limited. In particular, we study signaling under a symmetry or an independence assumption on the distribution of utility values for the actions. For symmetric distributions, we provide a novel characterization of the optimal signaling scheme. It results in a polynomial-time algorithm to compute an optimal scheme for many compactly represented symmetric distributions. In the independent case, we design a constant-factor approximation algorithm, which stands in marked contrast to the hardness of approximation in the general case. [ABSTRACT FROM AUTHOR]

In "Dynamic Stochastic Matching Under Limited Time," Aouad and Sarıtaç analyze the design of matching policies in dynamic markets such as carpooling platforms and kidney exchange schemes. A crucial distinction with previous literature is that the agents' arrivals and departures are fully dynamic. The demand and supply side are constantly replenished; each market participant remains available for potential matches during a limited period of time. Specifically, the authors formulate a general dynamic matching model over edge-weighted graphs, where the agents' arrivals and abandonments are stochastic and heterogeneous. The platform controls how long each agent waits and whom s/he is matched with. These decisions are subject to a fundamental tradeoff between increasing market thickness and mitigating the risk of abandonments from certain participants. The authors' main contribution is to devise simple matching algorithms with strong performance guarantees for a broad class of networks. In contrast, they show that widely used batching algorithms have an arbitrary bad performance on certain graph-theoretic structures. Their analysis involves novel techniques including linear programming benchmarks, value function approximations, and proxies for continuous-time Markov chains, which may be of broader interest. Extensive simulations on real-world taxi demand data demonstrate that the newly developed algorithms can significantly improve cost efficiency against batching algorithms. In centralized matching markets such as carpooling platforms and kidney exchange schemes, new participants constantly enter the market and remain available for potential matches during a limited period of time. To reach an efficient allocation, the "timing" of the matching decisions is a critical aspect of the platform's operations. There is a fundamental tradeoff between increasing market thickness and mitigating the risk that participants abandon the market. Nonetheless, the dynamic properties of matching markets have been mostly overlooked in the algorithmic literature. In this paper, we introduce a general dynamic matching model over edge-weighted graphs, where the agents' arrivals and abandonments are stochastic and heterogeneous. Our main contribution is to design simple matching algorithms that admit strong worst-case performance guarantees for a broad class of graphs. In contrast, we show that the performance of widely used batching algorithms can be arbitrarily bad on certain graph-theoretic structures motivated by carpooling services. Our approach involves the development of a host of new techniques, including linear programming benchmarks, value function approximations, and proxies for continuous-time Markov chains, which may be of broader interest. In extensive experiments, we simulate the matching operations of a car-pooling platform using real-world taxi demand data. The newly developed algorithms can significantly improve cost efficiency against batching algorithms. [ABSTRACT FROM AUTHOR]

In the presence of contagion, decision makers strategize about where in a network to intervene (e.g., seeding a new product). A large literature has developed methods for approximately optimizing the choice of k seeds to cause the largest cascade of, for example, product adoption. However, it is often impractical to measure an entire social network. In "Seeding with Costly Network Information," Eckles, Esfandiari, Mossel, and Rahimian develop and analyze algorithms for making a bounded number of queries of a social network and then selecting k seeds. They prove hardness results for this problem and provide almost tight approximation guarantees for their proposed algorithms under widely used models of contagion. One proposed algorithm is practical for both querying online social networks and structuring in-person surveys. This framework further allows reasoning about tradeoffs between spending budget on collecting more network data versus increasing the number of seeds. We study the task of selecting k nodes, in a social network of size n, to seed a diffusion with maximum expected spread size, under the independent cascade model with cascade probability p. Most of the previous work on this problem (known as influence maximization) focuses on efficient algorithms to approximate the optimal seed set with provable guarantees given knowledge of the entire network; however, obtaining full knowledge of the network is often very costly in practice. Here we develop algorithms and guarantees for approximating the optimal seed set while bounding how much network information is collected. First, we study the achievable guarantees using a sublinear influence sample size. We provide an almost tight approximation algorithm with an additive ε n loss and show that the squared dependence of sample size on k is asymptotically optimal when ε is small. We then propose a probing algorithm that queries edges from the graph and use them to find a seed set with the same almost tight approximation guarantee. We also provide a matching (up to logarithmic factors) lower-bound on the required number of edges. This algorithm is implementable in field surveys or in crawling online networks. Our probing takes p as an input which may not be known in advance, and we show how to down-sample the probed edges to match the best estimate of p if they are collected with a higher probability. Finally, we test our algorithms on an empirical network to quantify the tradeoff between the cost of obtaining more refined network information and the benefit of the added information for guiding improved seeding strategies. [ABSTRACT FROM AUTHOR]

We consider a large family of problems in which an ordering (or, more precisely, a chain of subsets) of a finite set must be chosen to minimize some weighted sum of costs. This family includes variations of min sum set cover, several scheduling and search problems, and problems in Boolean function evaluation. We define a new problem, called the min sum ordering problem (MSOP), which generalizes all these problems using a cost and a weight function defined on subsets of a finite set. Assuming a polynomial time α-approximation algorithm for the problem of finding a subset whose ratio of weight to cost is maximal, we show that under very minimal assumptions, there is a polynomial time 4 α -approximation algorithm for MSOP. This approximation result generalizes a proof technique used for several distinct problems in the literature. We apply this to obtain a number of new approximation results. Summary of Contribution: This paper provides a general framework for min sum ordering problems. Within the realm of theoretical computer science, these problems include min sum set cover and its generalizations, as well as problems in Boolean function evaluation. On the operations research side, they include problems in search theory and scheduling. We present and analyze a very general algorithm for these problems, unifying several previous results on various min sum ordering problems and resulting in new constant factor guarantees for others. [ABSTRACT FROM AUTHOR]

A New Method for Dynamic Learning and Doing For a large class of learning-and-doing problems, two processes are intertwined in the analysis: a forward process that updates the decision maker's belief or estimate of the unknown parameter, and a backward process that computes the expected future values. The mainstream literature focuses on the former process. In contrast, in "Dynamic Learning and Decision Making via Basis Weight Vectors," Hao Zhang proposes a new method based on pure backward induction on the continuation values created by feasible continuation policies. When the unknown parameter is a continuous variable, the method represents each continuation-value function by a vector of weights placed on a set of basis functions. The weight vectors that are potentially useful for the optimal solution can be found backward in time exactly (for very small problems) or approximately (for larger problems). A simulation study demonstrates that an approximation algorithm based on this method outperforms some popular algorithms in the linear contextual bandit literature when the learning horizon is short. This paper presents a new methodology to solve a general model of dynamic decision making with a continuous unknown parameter or state. The methodology centers on the "continuation-value functions" (mappings from the parameter space to the continuation-value space), created by feasible continuation policies. When the model primitives can be described through a family of basis functions (e.g., polynomials), a continuation-value function retains that property and can be represented by a basis weight vector. The set of efficient basis weight vectors can be constructed through backward induction, which leads to a significant reduction of problem complexity and enables an exact solution for small-sized problems. A set of approximation methods based on the new methodology is developed to tackle larger problems. The methodology is also extended to the multidimensional (multiparameter) setting, which features the problem of contextual multiarmed bandits with linear expected rewards. The approximation algorithm developed in this paper outperforms three benchmark algorithms (epsilon-greedy, Thompson sampling, and LinUCB) in learning situations with many actions and short horizons. [ABSTRACT FROM AUTHOR]

We consider the following general network design problem. The input is an asymmetric metric (V, c), root r ∈ V , monotone submodular function f : 2 V → R + , and budget B. The goal is to find an r-rooted arborescence T of cost at most B that maximizes f(T). Our main result is a simple quasi-polynomial time O (log k log log k) -approximation algorithm for this problem, in which k ≤ | V | is the number of vertices in an optimal solution. As a consequence, we obtain an O ( log 2 k log log k) -approximation algorithm for directed (polymatroid) Steiner tree in quasi-polynomial time. We also extend our main result to a setting with additional length bounds at vertices, which leads to improved O ( log 2 k log log k) -approximation algorithms for the single-source buy-at-bulk and priority Steiner tree problems. For the usual directed Steiner tree problem, our result matches the best previous approximation ratio but improves significantly on the running time. For polymatroid Steiner tree and single-source buy-at-bulk, our result improves prior approximation ratios by a logarithmic factor. For directed priority Steiner tree, our result seems to be the first nontrivial approximation ratio. Under certain complexity assumptions, our approximation ratios are the best possible (up to constant factors). [ABSTRACT FROM AUTHOR]