Search

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]

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]

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 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]

In large-scale disasters, evacuation using public transport, such as buses, is always essential, especially with limitations on the time window and resources available. Unfortunately, a Bus Evacuation Problem (BEP) is NP-hard in nature. This means it is impossible to find an optimal evacuation plan within a reasonable time window. Therefore, it is efficacious and requisite to use an approximation algorithm such that a sub-optimal plan can be derived quickly in large-scale disasters. In the literature, an approximation algorithm for BEP has been presented. However, there is not only a lack of rigorous proof of the approximation ratio, but also the computation time of the approximation algorithm is influenced by the number of evacuees. In this work, firstly the approximation ratio is derived as 2 n b + 7 , where n b is the number of buses, which is fundamentally more precise than the existing work. Further, the approximation ratio can be reduced to n b + 6 through a new proof provided in this work. More importantly, a new approximation algorithm is proposed in this work, with an aggregated network flow model that can be quickly solved as a linear programming problem in polynomial time. The approximation ratio of the new algorithm is proven to be n b + 1 when there is a pile of buses, and the computation time is insensitive to the number of evacuees. Finally, 10 sets of random cases and a real-life disaster, the flooding in Xingguo, China in 2019 are studied to illustrate the efficiency and practical applicability of the proposed approximation algorithm. [ABSTRACT FROM AUTHOR]