Search

The set cover problem has been studied extensively for many years. Submodular function plays a key role in combinatorial optimization. Extending the set cover problem, we consider three submodular cover problems. The first two problems minimize linear and submodular functions, respectively, subject to the same non-submodular cover constraint. The third problem minimizes a submodular function subject to non-submodular cover and precedence constraints. Based on the concepts of submodular ratio and gap, and Lovász extension, we devise greedy and primal–dual approximation algorithms for these problems. [ABSTRACT FROM AUTHOR]

This paper investigates the three-stage assembly flow shop scheduling problem, provided that there is a fixed maintenance period (MP) imposed on one of the machines in the first stage, the objective is to minimize the makespan. The starting time and duration of MP are known in advance, during MP no job can be processed on the corresponding machine. Only the non-resumable scenario is considered, i.e., if a job fails to finish before MP, it must restart from the beginning after the machine becomes available again, rather than continuing its processing. The problem generalizes the three-stage assembly flow shop scheduling problem without MPs and is therefore strongly NP-hard. To the best of our knowledge, the problem has not been explored so far. We propose three approximation algorithms for the problem. [ABSTRACT FROM AUTHOR]

In malleable job scheduling, jobs can be executed simultaneously on multiple machines with the processing time depending on the number of allocated machines. In this setting, jobs are required to be executed non-preemptively and in unison, in the sense that they occupy, during their execution, the same time interval over all the machines of the allocated set. In this work, we study generalizations of malleable job scheduling inspired by standard scheduling on unrelated machines. Specifically, we introduce a general model of malleable job scheduling, where each machine has a (possibly different) speed for each job, and the processing time of a job j on a set of allocated machines S depends on the total speed of S with respect to j. For machines with unrelated speeds, we show that the optimal makespan cannot be approximated within a factor less than e e - 1 , unless P = N P . On the positive side, we present polynomial-time algorithms with approximation ratios 2 e e - 1 for machines with unrelated speeds, 3 for machines with uniform speeds, and 7/3 for restricted assignments on identical machines. Our algorithms are based on deterministic LP rounding. They result in sparse schedules, in the sense that each machine shares at most one job with other machines. We also prove lower bounds on the integrality gap of 1 + φ for unrelated speeds (φ is the golden ratio) and 2 for uniform speeds and restricted assignments. To indicate the generality of our approach, we show that it also yields constant factor approximation algorithms for a variant where we determine the effective speed of a set of allocated machines based on the L p norm of their speeds. [ABSTRACT FROM AUTHOR]

Constrained partially observable Markov decision processes (CPOMDPs) have been used to model various real-world phenomena. However, they are notoriously difficult to solve to optimality, and there exist only a few approximation methods for obtaining high-quality solutions. In this study, grid-based approximations are used in combination with linear programming (LP) models to generate approximate policies for CPOMDPs. A detailed numerical study is conducted with six CPOMDP problem instances considering both their finite and infinite horizon formulations. The quality of approximation algorithms for solving unconstrained POMDP problems is established through a comparative analysis with exact solution methods. Then, the performance of the LP-based CPOMDP solution approaches for varying budget levels is evaluated. Finally, the flexibility of LP-based approaches is demonstrated by applying deterministic policy constraints, and a detailed investigation into their impact on rewards and CPU run time is provided. For most of the finite horizon problems, deterministic policy constraints are found to have little impact on expected reward, but they introduce a significant increase to CPU run time. For infinite horizon problems, the reverse is observed: deterministic policies tend to yield lower expected total rewards than their stochastic counterparts, but the impact of deterministic constraints on CPU run time is negligible in this case. Overall, these results demonstrate that LP models can effectively generate approximate policies for both finite and infinite horizon problems while providing the flexibility to incorporate various additional constraints into the underlying model. [ABSTRACT FROM AUTHOR]

Fractional derivative gives important tools to fit the real data with mathematical models because of the fractional parameters. This article introduces an algorithm for the approximation of solutions to linear and nonlinear fuzzy fractional initial value problems, specifically those involving the Caputo-Katugampola (CK) derivative, a generalized fractional derivative. The CK fractional derivative, characterized by two parameters, extends the capabilities of Caputo and Caputo-Hadamard fractional derivatives. The Optimal Homotopy Asymptotic Method (OHAM) is employed as an approximate analytic technique, offering multiple convergent control parameters to fine-tune solution convergence and accuracy. The article also addresses the representation of environmental uncertainty within the solution using Zadeh's fuzzy theory extension principle. This algorithm not only introduces the fuzzy fractional differential with the CK derivative but also provides a convergent analytic solution with minimal residual error. This contribution aims to support researchers in refining mathematical models to better align with real-world data. Three examples are considered to demonstrate the efficiency of the algorithm with several figures and tables. [ABSTRACT FROM AUTHOR]

In this paper we consider the coupled task scheduling problem with exact delay times on a single machine with the objective of minimizing the total completion time of the jobs. We provide constant-factor approximation algorithms for several variants of this problem that are known to be N P -hard, while also proving N P -hardness for two variants whose complexity was unknown before. Using these results, together with constant-factor approximations for the makespan objective from the literature, we also introduce the first results on bi-objective approximation in the coupled task setting. [ABSTRACT FROM AUTHOR]

The minimum vertex cover (MVC) problem is a canonical NP-hard combinatorial optimization problem aiming to find the smallest set of vertices such that every edge has at least one endpoint in the set. This problem has extensive applications in cybersecurity, scheduling, and monitoring link failures in wireless sensor networks (WSNs). Numerous local search algorithms have been proposed to obtain "good" vertex coverage. However, due to the NP-hard nature, it is challenging to efficiently solve the MVC problem, especially on large graphs. In this paper, we propose an efficient local search algorithm for MVC called TIVC, which is based on two main ideas: a 3-improvements (TI) framework with a tiny perturbation and edge selection strategy. We conducted experiments on real-world large instances of a massive graph benchmark. Compared with three state-of-the-art MVC algorithms, TIVC shows superior performance in accuracy and possesses a remarkable ability to identify significantly smaller vertex covers on many graphs. [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]

This paper proposes an approximation algorithm based on the Legendre and Chebyshev artificial neural network to explore the approximate solution of fractional Lienard and Duffing equations with a Caputo fractional derivative. These equations show the oscillating circuit and generalize the spring–mass device equation. The proposed approach transforms the given nonlinear fractional differential equation (FDE) into an unconstrained minimization problem. The simulated annealing (SA) algorithm minimizes the mean square error. The proposed techniques examine various non-integer order problems to verify the theoretical results. The numerical results show that the proposed approach yields better results than existing methods. [ABSTRACT FROM AUTHOR]

Abnormal electromagnetic radiation associated with seismic activity has been reported across a wide range of frequencies, but its primary energy is concentrated in the super-low-frequency (SLF) and extremely low-frequency (ELF) bands. To estimate the effect of the seismic radiation source, a radiator in a soil foundation was modeled as a horizontal electric dipole (HED), and the propagation characteristics of the electromagnetic fields were studied in the Earth–ionosphere cavity. The expressions of the electromagnetic fields could be obtained according to the reciprocity theorem. Therefore, a new algorithm named the numerical integral algorithm was proposed, which is suitable for both the SLF and ELF bands. The new algorithm was compared with the asymptotic approximation algorithm when the receiving point was not close to the field source and the antipode. The two algorithms were found to be in excellent agreement, confirming the validity of the new algorithm for SLF and ELF bands. [ABSTRACT FROM AUTHOR]

The problem of deletion of vertices to a hereditary graph class is a well-studied problem in parameterized complexity. Recently, a natural extension of the problem was initiated where we are given a finite set of hereditary graph classes and we determine whether k vertices can be deleted from a given graph so that the connected components of the resulting graph belong to one of the given hereditary graph classes. The problem is shown to be fixed parameter tractable (FPT) when the deletion problem to each of the given hereditary graph classes is fixed-parameter tractable, and the property of being in any of the graph classes is expressible in the counting monodic second order (CMSO) logic. This paper focuses on pairs of specific graph classes (Π 1 , Π 2) in which we would like the connected components of the resulting graph to belong to, and design simpler and more efficient FPT algorithms. [ABSTRACT FROM AUTHOR]

We generalize the tree doubling and Christofides algorithm to parameterized approximations for ATSP (constant factor approximations that invest more runtime with respect to a chosen parameter). The parameters we consider are upper bounded by the number of asymmetric distances , which yields algorithms to efficiently compute good approximations for moderately asymmetric TSP instances. As generalization of the Christofides algorithm, we derive a parameterized 2.5-approximation, with the size of a vertex cover for the subgraph induced by the edges with asymmetric distances as parameter. Our generalization of tree doubling gives a parameterized 3-approximation, where the parameter is the minimum number of asymmetric distances in a minimum spanning arborescence. Further, we combine these with a notion of symmetry relaxation which allows to trade approximation guarantee for runtime. Since the parameters we consider are theoretically incomparable, we present experimental results showing that generalized tree doubling frequently outperforms generalized Christofides with respect to parameter size. [ABSTRACT FROM AUTHOR]

A widely-studied deep reinforcement learning (RL) technique known as Prioritized Experience Replay (PER) allows agents to learn from transitions sampled with non-uniform probability proportional to their temporal-difference (TD) error. Although it has been shown that PER is one of the most crucial components for the overall performance of deep RL methods in discrete action domains, many empirical studies indicate that it considerably underperforms off-policy actor-critic algorithms. We theoretically show that actor networks cannot be effectively trained with transitions that have large TD errors. As a result, the approximate policy gradient computed under the Q-network diverges from the actual gradient computed under the optimal Q-function. Motivated by this, we introduce a novel experience replay sampling framework for actor-critic methods, which also regards issues with stability and recent findings behind the poor empirical performance of PER. The introduced algorithm suggests a new branch of improvements to PER and schedules effective and efficient training for both actor and critic networks. An extensive set of experiments verifies our theoretical findings, showing that our method outperforms competing approaches and achieves state-of-the-art results over the standard off-policy actor-critic algorithms. [ABSTRACT FROM AUTHOR]

Clustering with outliers is one of the most fundamental problems in Computer Science. Given a set X of n points and two numbers k,m, the clustering with outliers aims to exclude m points from X and partition the remaining points into k clusters that minimizes a certain cost function. In this paper, we give a general approach for solving clustering with outliers, which results in a fixed-parameter tractable (FPT) algorithm in k and m--i.e., an algorithm with running time of the form f(k,m) · nO(1) for some function f--that almost matches the approximation ratio for its outlier-free counterpart. As a corollary, we obtain FPT approximation algorithms with optimal approximation ratios for k-Median and k-Means with outliers in general and Euclidean metrics. We also exhibit more applications of our approach to other variants of the problem that impose additional constraints on the clustering, such as fairness or matroid constraints. [ABSTRACT FROM AUTHOR]

In this paper, we propose some new semidefinite relaxations for a class of nonconvex complex quadratic programming problems, which widely appear in the areas of signal processing and power system. By deriving new valid constraints to the matrix variables in the lifted space, we derive some enhanced semidefinite relaxations of the complex quadratic programming problems. Then, we compare the proposed semidefinite relaxations with existing ones, and show that the newly proposed semidefinite relaxations could be strictly tighter than the previous ones. Moreover, the proposed semidefinite relaxations can be applied to more general cases of complex quadratic programming problems, whereas the previous ones are only designed for special cases. Numerical results indicate that the proposed semidefinite relaxations not only provide tighter relaxation bounds, but also improve some existing approximation algorithms by finding better sub-optimal solutions. [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]

Voronoi diagrams on triangulated surfaces based on the geodesic metric play a key role in many applications of computer graphics. Previous methods of constructing such Voronoi diagrams generally depended on having an exact geodesic metric. However, exact geodesic computation is time-consuming and has high memory usage, limiting wider application of geodesic Voronoi diagrams (GVDs). In order to overcome this issue, instead of using exact methods, we reformulate a graph method based on Steiner point insertion, as an effective way to obtain geodesic distances. Further, since a bisector comprises hyperbolic and line segments, we utilize Apollonius diagrams to encode complicated structures, enabling Voronoi diagrams to encode a medial-axis surface for a dense set of boundary samples. Based on these strategies, we present an approximation algorithm for efficient Voronoi diagram construction on triangulated surfaces. We also suggest a measure for evaluating similarity of our results to the exact GVD. Although our GVD results are constructed using approximate geodesic distances, we can get GVD results similar to exact results by inserting Steiner points on triangle edges. Experimental results on many 3D models indicate the improved speed and memory requirements compared to previous leading methods. [ABSTRACT FROM AUTHOR]

The paper presents two effective methods for discovering process models in the form of partial differential equations based on an evolutionary algorithm and an algorithm for the best subset selection. The methods are designed to work with sparse and noisy data and implement various numerical differentiation techniques, including piecewise local approximation using multidimensional polynomial functions, neural network approximation, and an additional algorithm for selecting differentiation steps. To verify the algorithms, the experiment is carried out on pulsed heating of a viscous liquid (glycerol) by a submerged horizontal cylindrical heat source. Temperature measurements are taken only at six points, which makes the data very sparse. The noise level ranges from 0.2 to 1% of the observed maximum temperature. The algorithms can successfully restore the structure of the heat transfer equation in cylindrical coordinates and determine the thermal diffusivity coefficient with an error of 2.5–20%, depending on the algorithm type and heating mode. Additional synthetic setups are employed to analyze the dependence of accuracy on the noise level. Results also demonstrate the algorithms' ability to identify underlying processes such as convective motion. [ABSTRACT FROM AUTHOR]

Recently, complicated spatial search algorithms have emerged as spatial-information-based applications, such as location-based services (LBS), and have become very diverse and frequent. The aggregate nearest neighbor (ANN) search is an extension of the existing nearest neighbor (NN) search; it finds the object p * that minimizes G { d (p * , q i) , q i ∈ Q } from a set Q of M (≥1) query objects, where G is an aggregate function and d () is the distance between two objects. The flexible aggregate nearest neighbor (FANN) search is an extension of the ANN search by introducing flexibility factor  ϕ (0 < ϕ ≤ 1) ; it finds the object p * that minimizes G { d (p * , q i) , q i ∈ Q ϕ } from Q ϕ , a subset of Q with | Q ϕ | = ϕ | Q | . This paper proposes an efficient ϵ -approximate k-FANN (k ≥ 1) search algorithm for an arbitrary approximation ratio ϵ (≥1) in road networks. In general, ϵ -approximate algorithms are expected to give an improved search performance at the cost of allowing an error ratio of up to the given ϵ. Since the optimal value of ϵ varies greatly depending on applications and cases, the approximate algorithm for an arbitrary ϵ is essential. We prove that the error ratios of the approximate FANN objects returned by our algorithm do not exceed the given ϵ. To the best of our knowledge, our algorithm is the first ϵ -approximate k-FANN search algorithm in road networks for an arbitrary ϵ. Through a series of experiments using various real-world road network datasets, we demonstrated that our approximate algorithm always outperformed the previous state-of-the-art exact algorithm and that the error ratios of the approximate FANN objects were significantly lower than the given ϵ value. [ABSTRACT FROM AUTHOR]

Integrated satellite-terrestrial network (ISTN) has been considered a novel network architecture to achieve global three-dimensional coverage and ultra-wide area broadband access anytime and anywhere. Being a promising paradigm, cloud computing and mobile edge computing (MEC) have been identified as key technology enablers for ISTN to further improve quality of service and business continuity. However, most of the existing ISTN studies based on cloud computing and MEC regard satellite networks as relay networks, ignoring the feasibility of directly deploying cloud computing nodes and edge computing nodes on satellites. In addition, most computing tasks are transferred to cloud servers or offloaded to nearby edge servers, the layered design of integrated satellite-air-terrestrial architecture and the cloudedge-device cooperative processing problems have not been fully considered. Therefore, different from previous works, this paper proposed a novel satelliteair-terrestrial layered architecture for cloud-edge-device collaboration, named SATCECN. Then this paper analyzes the appropriate deployment locations of cloud servers and edge servers in ISTN, and describes the processing flow of typical satellite computing tasks. For computing resource allocation problems, this paper proposed a device-edge-cloud Multi-node Cross-layer Collaboration Computing (MCCC) method to find the optimal task allocation strategy that minimizes the task completion delay and the weighted system energy consumption. Furthermore, the approximate optimal solutions of the optimization model are obtained by using successive convex approximation algorithm, and the outstanding advantages of the proposed method in reducing system energy consumption and task execution delay are verified through experiments. Finally, some potential issues and directions for future research are highlighted. [ABSTRACT FROM AUTHOR]

The edit distance between two strings is defined as the smallest number of insertions, deletions, and substitutions that need to be made to transform one of the strings to another one. Approximating edit distance in subquadratic time is "one of the biggest unsolved problems in the field of combinatorial pattern matching" [37]. Our main result is a quantum constant approximation algorithm for computing the edit distance in truly subquadratic time. More precisely, we give an O(n1.810) quantum algorithm that approximates the edit distance within a factor of 3. We further extend this result to an O(n1.708) quantum algorithm that approximates the edit distance within a larger constant factor. Our solutions are based on a framework for approximating edit distance in parallel settings. This framework requires as black box an algorithm that computes the distances of several smaller strings all at once. For a quantum algorithm, we reduce the black box to metric estimation and provide efficient algorithms for approximating it.We further show that this framework enables us to approximate edit distance in distributed settings. To this end, we provide a MapReduce algorithm to approximate edit distance within a factor of 1+∈, with sublinearly many machines and sublinear memory. Also, our algorithm runs in a logarithmic number of rounds. [ABSTRACT FROM AUTHOR]

A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for Maximum Cliqe on unit disk graphs [Clark, Colbourn, Johnson; Discrete Mathematics '90]. Since then, it has been an intriguing open question whether or not tractability can be extended to general disk graphs. We show that the disjoint union of two odd cycles is never the complement of a disk graph nor of a unit (3-dimensional) ball graph. From that fact and existing results, we derive a simple QPTAS and a subexponential algorithm running in time 2õ (n²/3 ) for Maximum Cliqe on disk and unit ball graphs. We then obtain a randomized EPTAS for computing the independence number on graphs having no disjoint union of two odd cycles as an induced subgraph, bounded VC-dimension, and linear independence number. This, in combination with our structural results, yields a randomized EPTAS for Max Cliqe on disk and unit ball graphs. Max Cliqe on unit ball graphs is equivalent to finding, given a collection of points in R³, a maximum subset of pointswith diameter at most some fixed value. In stark contrast, Maximum Cliqe on ball graphs and unit 4-dimensional ball graphs, as well as intersection graphs of filled ellipses (even close to unit disks) or filled triangles is unlikely to have such algorithms. Indeed, we showthat, for all those problems, there is a constant ratio of approximation that cannot be attained even in time 2n1-ε, unless the Exponential Time Hypothesis fails. [ABSTRACT FROM AUTHOR]

In this article, we study the geometry of units and ideals of cyclotomic rings and derive an algorithm to find a mildly short vector in any given cyclotomic ideal lattice in quantum polynomial time, under some plausible number-theoretic assumptions. More precisely, given an ideal lattice of the cyclotomic ring of conductor m, the algorithm finds an approximation of the shortest vector by a factor exp(-õ (vm)). This result exposes an unexpected hardness gap between these structured lattices and general lattices: The best known polynomial time generic lattice algorithms can only reach an approximation factor exp(-O (m)). Following a recent series of attacks, these results call into question the hardness of various problems over structured lattices, suchas Ideal-SVP and Ring-LWE, upon which relies the security of a number of cryptographic schemes. [ABSTRACT FROM AUTHOR]

Fuzzy rough set theory has been successfully applied to many attribute reduction methods, in which the lower approximation set plays a pivotal role. However, the definition of lower approximation used has ignored the information conveyed by the upper approximation and the boundary region. This oversight has resulted in an unreasonable relation representation of the target set. Despite the fact that scholars have proposed numerous enhancements to rough set models, such as the variable precision model, none have successfully resolved the issues inherent in the classical models. To address this limitation, this paper proposes an unsupervised attribute reduction algorithm for mixed data based on an improved optimal approximation set. Firstly, the theory of an improved optimal approximation set and its associated algorithm are proposed. Subsequently, we extend the classical theory of optimal approximation sets to fuzzy rough set theory, leading to the development of a fuzzy improved approximation set method. Finally, building on the proposed theory, we introduce a novel, fuzzy optimal approximation-set-based unsupervised attribute reduction algorithm (FOUAR). Comparative experiments conducted with all the proposed algorithms indicate the efficacy of FOUAR in selecting fewer attributes while maintaining and improving the performance of the machine learning algorithm. Furthermore, they highlight the advantage of the improved optimal approximation set algorithm, which offers higher similarity to the target set and provides a more concise expression. [ABSTRACT FROM AUTHOR]

With the advancement of space technology and satellite communications, low-Earth-orbit (LEO) satellite networks have experienced rapid development in the past decade. In the vision of 6G, LEO satellite networks play an important role in future 6G networks. On the other hand, a variety of applications, including many delay-sensitive applications, are continuously emerging. Due to the highly dynamic nature of LEO satellite networks, supporting time-deterministic services in such networks is challenging. However, we can provide latency guarantees for most delay-sensitive applications through data plane traffic shaping and control plane routing optimization. This paper addresses the routing optimization problem for time-sensitive (TS) flows in software-defined low-Earth-orbit (LEO) satellite networks. We model the problem as an integer linear programming (ILP) model aiming to minimize path handovers and maximum link utilization while meeting TS flow latency constraints. Since this problem is NP-hard, we design an efficient longest continuous path (LCP) approximation algorithm. LCP selects the longest valid path in each topology snapshot that satisfies delay constraints. An auxiliary graph then determines the routing sequence with minimized handovers. We implement an LEO satellite network testbed with Open vSwitch (OVS) and an open-network operating system (ONOS) controller to evaluate LCP. The results show that LCP reduces the number of path handovers by up to 31.7% and keeps the maximum link utilization lowest for more than 75% of the time compared to benchmark algorithms. In summary, LCP achieves excellent path handover optimization and load balancing performance under TS flow latency constraints. [ABSTRACT FROM AUTHOR]

Due to the advantages such as high flexibility, low cost and easy implementation offered by unmanned aerial vehicles (UAVs), a UAV-assisted network is regard as an appealing solution to a seamless coverage, high disaster-tolerant and on-demand wireless system. In this paper, we focus on the downlink transmission in a cache-enabled UAV-assisted wireless communication network, where UAVs cache popular content from a macro base station in advance and cooperatively transfer the content to users. We aim to minimize the average transmission latency of the system and to formulate an optimization problem that jointly optimizes the UAV location, beamforming and caching strategy. However, the formulated problem is very challenging because of its non-convexity and the highly coupled optimization variables. To solve this resulting problem efficiently, we decompose it into two subproblems, namely UAV location and beamforming optimization, and UAV caching strategy optimization. The first subproblem is an NP-hard joint optimization problem, while the second one is a linear programing problem. By adopting the first-order Taylor expansion, we propose a convex optimization algorithm based on the difference-of-convex (DC) method. Specifically, we bring out a method to apply linear approximation in the DC-based algorithm, which is particularly suitable to the problems involving complicated summations. The numerical results demonstrate that the proposed DC-based iterative optimization algorithm can efficiently reduce the average transmission latency of the system. [ABSTRACT FROM AUTHOR]

Motivation Many real-world problems can be modeled as annotated graphs. Scalable graph algorithms that extract actionable information from such data are in demand since these graphs are large, varying in topology, and have diverse node/edge annotations. When these graphs change over time they create dynamic graphs, and open the possibility to find patterns across different time points. In this article, we introduce a scalable algorithm that finds unique dense regions across time points in dynamic graphs. Such algorithms have applications in many different areas, including the biological, financial, and social domains. Results There are three important contributions to this manuscript. First, we designed a scalable algorithm, USNAP , to effectively identify dense subgraphs that are unique to a time stamp given a dynamic graph. Importantly, USNAP provides a lower bound of the density measure in each step of the greedy algorithm. Second, insights and understanding obtained from validating USNAP on real data show its effectiveness. While USNAP is domain independent, we applied it to four non-small cell lung cancer gene expression datasets. Stages in non-small cell lung cancer were modeled as dynamic graphs, and input to USNAP. Pathway enrichment analyses and comprehensive interpretations from literature show that USNAP identified biologically relevant mechanisms for different stages of cancer progression. Third, USNAP is scalable, and has a time complexity of O (m + m c   log   n c + n c   log   n c) ⁠ , where m is the number of edges, and n is the number of vertices in the dynamic graph; m c is the number of edges, and n c is the number of vertices in the collapsed graph. Availability and implementation The code of USNAP is available at https://www.cs.utoronto.ca/~juris/data/USNAP22. [ABSTRACT FROM AUTHOR]

In wireless sensor networks (WSNs), the virtual backbone (VB) consists of a subset of nodes, which are responsible for routing tasks. Fault-tolerant VBs are desirable for overcoming the effects of node or link failure in WSNs. Usually, a homogeneous WSN (VB) is abstracted as a unit disk graph (UDG) (connected dominating set(CDS)). This paper introduces the concept of a fault-tolerant CDS in a UDG called a ((2, 2), m)-CDS, which is different from a traditional fault-tolerant CDS ((k, m)-CDS). A ((2, 2), m)-CDS can still function even if one edge or one node fails, which implies that it possesses fault-tolerant properties for both nodes and edges, in contrast to traditional (k, m)-CDSs, which possess fault tolerance only for nodes. Then, we propose a 5 α -approximation algorithm for computing a ((2, 2), m)-CDS, where α is the performance ratio for computing a (2, m) -CDS, and analyze its time complexity. In simulations, we compare our algorithm with an existing algorithm for fault-tolerant CDS construction based on CDS size. From the simulations, we find that our algorithm outperforms its competitor in constructing a quality VB. [ABSTRACT FROM AUTHOR]

Trees with many leaves have applications for broadcasting a message to all recipients simultaneously. Internal nodes of a broadcasting tree require more expensive technology to forward the messages received. We address a problem that captures the main goal: finding spanning trees with few internal nodes in a given network. The Maximum Leaf Spanning Arborescence problem consists of, given a directed graph D , finding a spanning arborescence of D , if one exists, with the maximum number of leaves. This problem is NP-hard in general and MaxSNP-hard in the rooted directed acyclic graphs class. This paper explores a relationship between Maximum Leaf Spanning Arborescence in rooted directed acyclic graphs and maximum weight set packing. The latter problem is related to independent sets on particular classes of intersection graphs. Exploiting this relation, we derive a 7/5-approximation for Maximum Leaf Spanning Arborescence on rooted directed acyclic graphs, improving on the previous 3/2-approximation. [ABSTRACT FROM AUTHOR]

Recovering anomalous information covered under noise in late gates can enhance airborne transient electromagnetic (ATEM) detection. Conventional denoising mainly comprises filtering and gate correlation-based decomposition algorithms; the former fails to extract anomalies contaminated by noise and the latter relies on the correlation between gates, which may yield false late gate anomalies caused by early large-amplitude anomalies in early gates. In ATEM profiles, the correlation between anomalies in adjacent gates makes the anomalies to be measured to have low-rank characteristics relative to the noise-contaminated profiles; the noise is uniformly distributed in the profiles, which have nonlocal self-similarity. Therefore, the low-rank matrix approximation algorithm is applicable to ATEM data denoising. In this study, an algorithm—noise-whitening-based weighted nuclear norm minimization (NW-WNNM)—is designed to remove ATEM profile noise. First, we analyze the influence of patch size in block matching on anomalous and noisy patches and estimate the profile patch size adaptively. Then, we combine the estimation of noise variance in weighted nuclear norm minimization (WNNM) with the noise whitening of similar patch matrices to reduce the noise interference on the nuclear norm and add a whitening factor in the weight vector to make the soft-thresholding function applicable to the low-rank reconstruction of the whitened matrix. By analyzing the reconstructed low-rank matrix and its feature distribution, compared with WNNM, NW-WNNM can detect the feature information more accurately and eliminate the influence of noise on the nuclear norm. Simulation and field profile results indicate that NW-WNNM is superior to comparison denoising methods. [ABSTRACT FROM AUTHOR]

Given an undirected complete graph G = (V , E) on k n vertices with a non-negative weight function on E , the maximum-weight k -cycle (k -path) packing problem aims to compute a set of n vertex-disjoint cycles (paths) in G containing k vertices so that the total weight of the edges in these n cycles (paths) is maximized. For the maximum-weight k -cycle packing problem, we develop an algorithm achieving an approximation ratio of α ⋅ (k − 1 k) 2 , where α is the approximation ratio for the maximum traveling salesman problem. For the case k = 4 , we design a better 2 3 -approximation algorithm. When the weights of edges obey the triangle inequality, we propose a 3 4 -approximation algorithm and a 3 5 -approximation algorithm for the maximum-weight k -cycle packing problem with k = 4 and k = 5 , respectively. For the maximum-weight k -path packing problem with k = 3 (or k = 5) with the triangle inequality, we devise an algorithm with approximation ratio 3 4 and give a tight example. [ABSTRACT FROM AUTHOR]

We consider scheduling monotonic moldable tasks on multiple platforms, where each platform contains a set of processors. A moldable task can be split into several pieces of equal size and processed simultaneously on multiple processors. Tasks are not allowed to be processed spanning over platforms. This scheduling model has many applications, ranging from parallel computing to the berth and quay crane allocation and the workforce assignment problem. We develop several approximation algorithms aiming at minimizing the makespan. More precisely, we provide a 2-approximation algorithm for identical platforms, a Fully Polynomial Time Approximation Scheme (FPATS) under the assumption of large processor counts and a 2-approximation algorithm for a fixed number of heterogeneous platforms. Most of the proposed algorithms combine a dual approximation scheme with a novel approach to improve the dual approximation algorithm. All results can be extended to the contiguous case, i.e., a task can only be executed by contiguously numbered processors. [ABSTRACT FROM AUTHOR]

The article presents the development of new physics-informed evolutionary neural network learning algorithms. These algorithms aim to address the challenges of ill-posed problems by constructing a population close to the Pareto front. The study focuses on comparing the algorithm's capabilities based on three quality criteria of solutions. To evaluate the algorithms' performance, two benchmark problems have been used. The first involved solving the Laplace equation in square regions with discontinuous boundary conditions. The second problem considered the absence of boundary conditions but with the presence of measurements. Additionally, the study investigates the influence of hyperparameters on the final results. Comparisons have been made between the proposed algorithms and standard algorithms for constructing neural networks based on physics (commonly referred to as vanilla's algorithms). The results demonstrate the advantage of the proposed algorithms in achieving better performance when solving incorrectly posed problems. Furthermore, the proposed algorithms have the ability to identify specific solutions with the desired smoothness. [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]

Diversity maximization is a fundamental problem with broad applications in data summarization, web search, and recommender systems. Given a set X of n elements, the problem asks for a subset S of k ≪ n elements with maximum diversity, as quantified by the dissimilarities among the elements in S. In this paper, we study diversity maximization with fairness constraints in streaming and sliding-window models. Specifically, we focus on the max–min diversity maximization problem, which selects a subset S that maximizes the minimum distance (dissimilarity) between any pair of distinct elements within it. Assuming that the set X is partitioned into m disjoint groups by a specific sensitive attribute, e.g., sex or race, ensuring fairness requires that the selected subset S contains k i elements from each group i ∈ [ m ] . Although diversity maximization has been extensively studied, existing algorithms for fair max–min diversity maximization are inefficient for data streams. To address the problem, we first design efficient approximation algorithms for this problem in the (insert-only) streaming model, where data arrive one element at a time, and a solution should be computed based on the elements observed in one pass. Furthermore, we propose approximation algorithms for this problem in the sliding-window model, where only the latest w elements in the stream are considered for computation to capture the recency of the data. Experimental results on real-world and synthetic datasets show that our algorithms provide solutions of comparable quality to the state-of-the-art offline algorithms while running several orders of magnitude faster in the streaming and sliding-window settings. [ABSTRACT FROM AUTHOR]

In this article, we give the sharp bounds of probabilistic Kolmogorov N , δ -widths and probabilistic linear N , δ -widths of the multivariate Sobolev space W 2 A with common smoothness on a S q norm equipped with the Gaussian measure μ , where A ⊂ R d is a finite set. And we obtain the sharp bounds of average width from the results of the probabilistic widths. These results develop the theory of approximation of functions and play important roles in the research of related approximation algorithms for Sobolev spaces. [ABSTRACT FROM AUTHOR]

The minimization of an energy functional is the main ingredient of several segmentation and geometric modeling problems. When the solution of this kind of optimization problem is described by a curve, the most popular approach consists in representing the curve as a parametric curve and to compute the minimum in terms of the free parameters of the curve. In free form design tasks, the fairness (energy) functional depends of the arc length and the bending energy of the curve and the classical approach requires to compute first and second derivatives. This work presents a Hermite interpolating subdivision scheme, based on Bézier rational curves, with local tension parameters and discusses an efficient software implementation of the algorithm for energy minimization of the functional. The curve that minimizes the functional is called the fair curve, and it shows excellent properties to be used for design purposes. The novelty of the proposed method lies in the fact it is derivative free. Also we include a discussion of the implementation of our method and show some numerical results. [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]

It is well known that ω -circulant matrices with ω ≠ 0 can be simultaneously diagonalized by a transform matrix, which can be factored as the product of a diagonal matrix, depending on ω , and of the unitary matrix F n associated to the Fast Fourier Transform. Hence, all the sets of ω -circulants form algebras whose computational power, in terms of complexity, is the same as the classical circulants with ω = 1 . However, stability is a delicate issue, since the condition number of the transform is equal to that of the diagonal part, tending to max { | ω | , | ω | − 1 } . For ω = 0 , the set of related matrices is still an algebra, which is the algebra of lower triangular matrices, but they do not admit a common transform since most of them (all except the multiples of the identity) are non-diagonalizable. In the present work, we review two modern applications, ranging from parallel computing in preconditioning of PDE approximations to algorithms for subdivision schemes, and we emphasize the role of such algebra. For the two problems, few numerical tests are conducted and critically discussed and the related conclusions are drawn. [ABSTRACT FROM AUTHOR]

The three-dimensional (3D) angularity of coarse aggregates was investigated in this study by an optimal ellipsoid approximation algorithm. The minimum volume enclosing ellipsoid (MVEE) of the 3D coarse aggregate particle represented by the surface point cloud was computed by a Python program. An algorithm was proposed to compute the optimal ellipsoid that is inscribed in the aggregate particle as far as possible. In the algorithm, a fitting index was proposed and a cycle program was coded to search the optimal ellipsoid. Based on the optimal ellipsoid and the point cloud of the coarse aggregate particle, a 3D angularity index was proposed. The critical discriminant coefficient was introduced into the angularity index to filter out the tiny convex parts on the particle. Six 3D geometric models were generated and five 3D aggregate particles were randomly selected to verify the effectiveness of the angularity index. The results demonstrate that the angularity index proposed in this study can effectively distinguish the angularity of different geometric models. The effect of mesh precision on the angularity index was analyzed and the critical discriminant coefficient was studied by the parameter analysis method and Delphi expert investigation method. [ABSTRACT FROM AUTHOR]

We consider the intractable problem of finding several edge-disjoint spanning trees of the minimum total weight with a given diameter in complete undirected graph in current paper. The weights of edges of a graph are random variables from several continuous distributions: uniform, biased truncated exponential, biased truncated normal. The approximation algorithm with time complexity (n2), where n is number of vertices in graph, is proposed for solving this problem. The asymptotic optimality conditions for constructed algorithm is presented for each considered probabilistic distribution. [ABSTRACT FROM AUTHOR]

This paper presents the distributed primal outer approximation (DiPOA) algorithm for solving sparse convex programming (SCP) problems with separable structures, efficiently, and in a decentralized manner. The DiPOA algorithm development consists of embedding the recently proposed relaxed hybrid alternating direction method of multipliers (RH-ADMM) algorithm into the outer approximation (OA) algorithm. We also propose two main improvements to control the quality and the number of cutting planes that approximate nonlinear functions. In particular, the RH-ADMM algorithm acts as a distributed numerical engine inside the DiPOA algorithm. DiPOA takes advantage of the multi-core architecture of modern processors to speed up optimization algorithms. The proposed distributed algorithm makes practical the solution of SCP in learning and control problems from the application side. This paper concludes with a performance analysis of DiPOA for the distributed sparse logistic regression and quadratically constrained optimization problems. Finally, the paper concludes with a numerical comparison with state-of-the-art optimization solvers. [ABSTRACT FROM AUTHOR]

The new iterative method of approximating the boundary trajectory of a short-focus electron beam propagating in a free drift mode in a low-pressure ionized gas under the condition of compensation of the space charge of electrons is considered and discussed in the article. To solve the given approximation task, the root-polynomial functions of the fourth and fifth order were applied, the main features of which are the ravine character and the presence of one global minimum. As an initial approach to solving the approximation problem, the values of the polynomial coefficients are calculated by solving the interpolation problem. After this, the approximation task is solved iteratively. All necessary polynomial coefficients are calculated multiple times, taking into account the values of the function and its derivative at the reference points. The final values of polynomial coefficients of high-order root-polynomial functions are calculated using the dichotomy method. The article also provides examples of the applying fourth-order and fifth-order root-polynomial functions to approximate sets of numerical data that correspond to the description of ravine functions. The obtained theoretical results are interesting and important for the experts who study the physics of electron beams and design modern industrial electron beam technological equipment. [ABSTRACT FROM AUTHOR]

The presented research addresses the problem of dependency analysis of the ultrasonic signal measured by a sensor in an engine oil bath. The dependency analysis is performed on a selected ultrasonic signal sensor solution containing its own generator and an ultrasonic signal receiver detecting the level of the oil in which it is immersed. The influence of the resulting amplitude of the received ultrasonic signal is mainly due to the level of the measured oil level and the oil temperature, as shown by the regression analysis and ANOVA (Analysis of Variance) testing performed. The analyzed dependence of the time determination of the length of the generated ultrasonic signal envelope is given by a set threshold value, which can be dynamically adjusted based on the backtracking evaluation. The analysis results in the form of approximation by the dependency algorithm confirm the assumption of possible standardization of the envelope parameters with the achievement of accuracy up to 99.02%. The analyzed parameters approximated by the temperature and oil level dependence algorithms include the amplitude of the measured signal, steepness of the rising edge, duration of the envelope, and the digitally processed amplitude value. [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]