Search

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]

Multiobjective optimization is a ubiquitous problem that arises naturally in many scientific and industrial areas. Network routing optimization with multiobjective performance demands falls into this problem class, and finding good quality solutions at large scales is generally challenging. In this work, we develop a scheme with which near-term quantum computers can be applied to solve multiobjective combinatorial optimization problems. We study the application of this scheme to the network routing problem in detail, by first mapping it to the multiobjective shortest-path problem. Focusing on an implementation based on the quantum approximate optimization algorithm (QAOA)—the go-to approach for tackling optimization problems on near-term quantum computers—we examine the Pareto plot that results from the scheme and qualitatively analyze its ability to produce Pareto-optimal solutions. We further provide theoretical and numerical scaling analyses of the resource requirements and performance of QAOA and identify key challenges associated with this approach. Finally, through Amazon Braket, we execute small-scale implementations of our scheme on the IonQ Harmony 11-qubit quantum computer.

We present improved deterministic algorithms for approximating shortest paths in the Congested Cliqe model of distributed computing. We obtain poly(log logn)-round algorithms for the following problems in unweighted undirected n-vertex graphs: • (1 + ϵ)-approximation of multi-source shortest paths (MSSP) from O(√n) sources. • (2 + ϵ)-approximation of all pairs shortest paths (APSP). • (1 + ϵ, β)-approximation of APSP where β = O... . These bounds improve exponentially over the state-of-the-art poly-logarithmic bounds due to [Censor-Hillel et al., PODC19]. It also provides the first nearly-additive bounds for the APSP problem in sub-polynomial time. Our approach is based on distinguishing between short and long distances based on some distance threshold t = O(...) where β = O(...). Handling the long distances is done by devising a new algorithm for computing a sparse (1 + ϵ, β) emulator with O(n log logn) edges. For the short distances, we provide distance-sensitive variants for the distance tool-kit of [Censor-Hillel et al., PODC19]. By exploiting the fact that this tool-kit should be applied only on local balls of radius t, their round complexities get improved from poly(logn) to poly(log t). Finally, our deterministic solutions for these problems are based on a derandomization scheme of a novel variant of the hitting set problem, which might be of independent interest. [ABSTRACT FROM AUTHOR]

The Connected Sensor Problem (CSP) presents a prevalent challenge in the realms of communication and Internet of Things (IoT) applications. Its primary aim is to maximize the coverage of users while maintaining connectivity among K sensors. Addressing the challenge of managing a large user base alongside a finite number of candidate locations, this paper proposes an extension to the CSP: the h-hop independently submodular maximization problem characterized by curvature α. We have developed an approximation algorithm that achieves a ratio of 1−e−α(2h+3)α. The efficacy of this algorithm is demonstrated on the CSP, where it shows superior performance over existing algorithms, marked by an average enhancement of 8.4%.

In this paper, we study the regular sensory data collection of Points of Interest (PoIs) with multiple Unmanned Aerial Vehicles (UAVs) during an extended monitoring period, where each PoI is visited multiple times before its data update deadline to keep the data fresh. We observe that most existing studies ignored the important differences in the data stored in the PoIs, scheduled a plan that dispatched UAVs to visit all PoIs before the same deadline, and simply repeated the plan during the monitoring period, which undoubtedly increased the service cost of the UAVs. Considering the specific data update deadline of each PoI, we formulate a novel UAV cost minimization problem to collect the data stored in each PoI before its deadline by finding a series of plans for UAVs such that the service cost of the UAVs during the monitoring period is minimized; the service cost of the UAVs is composed of the consumed energy of the UAVs utilized for hovering for data collection and the consumed energy of the UAVs utilized for flying. To deal with the above NP-hard problem, we devise an approximation algorithm by grouping the PoIs and accessing them in batches. Then, we analyze the proposed algorithm and evaluate the performance of the algorithm through experimental simulations. The experimental results show that the proposed algorithm is very promising. [ABSTRACT FROM AUTHOR]

Solving combinatorial problems on complex networks represents a primary issue which, on a large scale, requires the use of heuristics and approximate algorithms. Recently, neural methods have been proposed in this context to find feasible solutions for relevant computational problems over graphs. However, such methods have some drawbacks: (1) they use the same neural architecture for different combinatorial problems without introducing customizations that reflects the specificity of each problem; (2) they only use a nodes local information to compute the solution; (3) they do not take advantage of common heuristics or exact algorithms. Following this interest, in this research we address these three main points by designing a customized attention-based mechanism that uses both local and global information from the adjacency matrix to find approximate solutions for the Minimum Vertex Cover Problem. We evaluate our proposal with respect to a fast two-factor approximation algorithm and a widely adopted state-of-the-art heuristic both on synthetically generated instances and on benchmark graphs with different scales. Experimental results demonstrate that, on the one hand, the proposed methodology is able to outperform both the two-factor approximation algorithm and the heuristic on the test datasets, scaling even better than the heuristic with harder instances and, on the other hand, is able to provide a representation of the nodes which reflects the combinatorial structure of the problem. [ABSTRACT FROM AUTHOR]

This paper considers several two-machine open shop problems with two agents. Each agent has an independent set of nonpreemptive jobs, and the objective is to find either a schedule minimizing a linear combination of the makespans of both agents, a schedule minimizing the makespan of one agent with the makespan of the other agent not exceeding a threshold, or all Pareto-optimal schedules with respect to the makespans of both agents. We present a number of results for the problems above, including a polynomial algorithm and a pseudo-polynomial algorithm for special cases, non-approximability, two approximation algorithms, and a fully polynomial-time approximation scheme. Finally, we run numerical experiments to show the effectiveness of the pseudo-polynomial algorithm and the approximation algorithms. [ABSTRACT FROM AUTHOR]

Numerical algorithms for calculating the left- and right-sided Riemann–Liouville fractional integrals and the left- and right-sided fractional derivatives in the Caputo sense using spline interpolation techniques are derived. The spline of the fifth degree (the so-called quintic spline) is mainly taken into account, but the linear and cubic splines are also considered to compare the quality of the developed method and numerical calculations. The estimation of errors for the derived approximation algorithms is presented. Examples of the numerical evaluation of the fractional integrals and derivatives are executed using 128-bit floating-point numbers and arithmetic routines. For each derived algorithm, the experimental orders of convergence are calculated. Also, an illustrative computational example showing the action of the considered fractional operators on the symmetric function in the interval is presented. [ABSTRACT FROM AUTHOR]

Bayesian optimization algorithms are widely used for solving problems with a high computational complexity in terms of objective function evaluation. The efficiency of Bayesian optimization is strongly dependent on the quality of the surrogate models of an objective function, which are built and refined at each iteration. The quality of surrogate models, and hence the performance of an optimization algorithm, can be greatly improved by selecting the appropriate hyperparameter values of the approximation algorithm. The common approach to finding good hyperparameter values for each iteration of Bayesian optimization is to build surrogate models with different hyperparameter values and choose the best one based on some estimation of the approximation error, for example, a cross-validation score. Building multiple surrogate models for each iteration of Bayesian optimization is computationally demanding and significantly increases the time required to solve an optimization problem. This paper suggests a new approach, called exploratory landscape validation, to find good hyperparameter values with less computational effort. Exploratory landscape validation metrics can be used to predict the best hyperparameter values, which can improve both the quality of the solutions found by Bayesian optimization and the time needed to solve problems. [ABSTRACT FROM AUTHOR]

In this paper we analyze the links between the agent's reservation utility, bargaining power, and risk aversion in terms of their simultaneous effects on the structure of optimal static contracts. We compare the following principal-agent models in the symmetric and asymmetric information environments: the standard approach, which includes a participation constraint, and a multi-objective (MO) optimization approach in which the objective function is a convex combination of the expected utilities of the principal and the agent. The MO model does not include a participation constraint, but it includes a parameter for the agent's bargaining power. We also study an Evolutionary Algorithm implementation of the static principal-agent model to support and extend our analytical results. We show that the numerical solution approximated by our implementation of an evolutionary algorithm is in line with the analytical solutions mentioned before. That is, for every admissible value of the agent's reservation utility, there is a corresponding admissible value of the agent's bargaining parameter, both in the MO approach and the EA implementation. [ABSTRACT FROM AUTHOR]

Aiming to address problems such as low sampling success rate and long computation time in the motion planning of a dual-arm cooperative system with multiple constraints, this paper proposes an Informed-Bi-Quick RRT* algorithm based on offline sampling. First, in the process of pre-sampling, the new algorithm relaxes the approximation of constrained manifolds by introducing the idea of incremental construction, and it incorporates the stochastic gradient descent method to replace global random sampling with local random sampling, which enriches the data set and shortens the offline sampling time of the data set. Second, the new algorithm improves the original Quick-RRT* algorithm by combining the two-tree idea and the multi-target bias expansion strategy, and it improves the adaptability of the algorithm to different obstacle environments. In addition, the loosely constrained motion and tightly constrained motion in the two-arm cooperative system are analyzed, and the adaptive planning of the two-arm trajectory in different motions is described in detail. In this paper, the two-arm cooperative model constructed with UR5 and UR10 robot arms is studied, and the ability of the proposed algorithm to deal with multiple constraints is verified by simulating assembly and handling tasks. The experimental results show that compared with other methods, the proposed algorithm has obvious advantages in path quality and planning efficiency. [ABSTRACT FROM AUTHOR]

We consider bicriteria flowshop scheduling problems with two machines to simultaneously minimize the makespan and the total completion time without any prioritization between the two objectives. An approximation relative to the optimal value of the problem with regard to each objective is adopted, even though a schedule with both objectives reaching their minimum at the same time may not exist. We consider several problems with ordered aspects on processing times such as job ordered and machine ordered. For each problem, we propose a fast (ρ 1 , ρ 2) -approximation algorithm, where ρ 1 and ρ 2 indicate the approximation ratios with regard to the makespan and the total completion time, respectively, and we explore the problem's inapproximability region that cannot be reached by any algorithm. [ABSTRACT FROM AUTHOR]

We revisit a classical scheduling model to incorporate modern trends in data center networks and cloud services. Addressing some key challenges in the allocation of shared resources to user requests (jobs) in such settings, we consider the following variants of the classic resource allocation problem (RAP). The input to our problems is a set J of jobs and a set M of homogeneous hosts, each has an available amount of some resource. Assuming that time is slotted, a job is associated with a release time, a due date, a weight and a given length, as well as its resource requirement. A feasible schedule is an allocation of the resource to a subset of the jobs, satisfying the job release times/due dates as well as the resource constraints. A crucial distinction between classic RAP and our problems is that we allow preemption and migration of jobs, motivated by virtualization techniques. We consider two natural objectives: throughput maximization (MaxT), which seeks a maximum weight subset of the jobs that can be feasibly scheduled on the hosts in M, and resource minimization (MinR), that is finding the minimum number of (homogeneous) hosts needed to feasibly schedule all jobs. Both problems are known to be NP-hard. We first present an Ω (1) -approximation algorithm for MaxT instances where time-windows form a laminar family of intervals. We then extend the algorithm to handle instances with arbitrary time-windows, assuming there is sufficient slack for each job to be completed. For MinR we study a more general setting with d resources and derive an O (log d) -approximation for any fixed d ≥ 1 , under the assumption that time-windows are not too small. This assumption can be removed leading to a slightly worse ratio of O (log d log ∗ T) , where T is the maximum due date of any job. [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]

In recent years, variational quantum algorithms such as the Quantum Approximation Optimization Algorithm (QAOA) have gained popularity as they provide the hope of using NISQ devices to tackle hard combinatorial optimization problems. It is, however, known that at low depth, certain locality constraints of QAOA limit its performance. To go beyond these limitations, a non-local variant of QAOA, namely recursive QAOA (RQAOA), was proposed to improve the quality of approximate solutions. The RQAOA has been studied comparatively less than QAOA, and it is less understood, for instance, for what family of instances it may fail to provide high-quality solutions. However, as we are tackling NP-hard problems (specifically, the Ising spin model), it is expected that RQAOA does fail, raising the question of designing even better quantum algorithms for combinatorial optimization. In this spirit, we identify and analyze cases where (depth-1) RQAOA fails and, based on this, propose a reinforcement learning enhanced RQAOA variant (RL-RQAOA) that improves upon RQAOA. We show that the performance of RL-RQAOA improves over RQAOA: RL-RQAOA is strictly better on these identified instances where RQAOA underperforms and is similarly performing on instances where RQAOA is near-optimal. Our work exemplifies the potentially beneficial synergy between reinforcement learning and quantum (inspired) optimization in the design of new, even better heuristics for complex problems. [ABSTRACT FROM AUTHOR]

• A frequency-domain retracker with interface to In-Flight Point-Target-Response. • Assessment of the impact of In-Flight Point-Target-Response for Sentinel-6 MF. • The range walk correction applied via a Chirp-Zeta-Transform algorithm. • Assessment of the impact of the range-walk correction for Sentinel-6 MF. • A full Cal/Val of the first year of Sentinel-6 MF altimetry science data. Poseidon-4 is a dual-frequency redundant radar altimeter on board the European Commission Copernicus Programme Sentinel-6 Michael Freilich satellite, that represents a significant breakthrough with respect to its predecessors Jason-class altimeters due to its digital architecture and to its innovative measurements and calibration modes. In the framework of the Sentinel-6 Michael Freilich commissioning preparatory activities, CNES has contracted CLS for the development of a Sentinel-6 Processing Prototype (S6PP) application. S6PP is a multi-chain processing suite able to process Sentinel-6 Level-1A and Level-1B data products up to Level-2. The novel algorithms developed in the CNES/CLS research and development activities are implemented within S6PP and validated to support the different thematic applications (in particular inland water and ocean) and in view of promoting them for possible implementation in the operational ground segment. The present work covers in particular the main results over open ocean for the main altimetric geophysical variables over the sea surface (sea surface height anomaly, significant wave-height, sigma-nought and wind speed) derived by the Low-Resolution Mode (LRM) and High-Resolution Mode (HRM) chains of S6PP in terms of precision, accuracy, spectral content and measurement stability. Given the reported variation of the payload in-orbit temperatures along with the reported instrumental ageing, and given the tight requirement to measure the GMSL (Global Mean Sea Level) in seamless continuity with Jason-3, the clear goal for S6PP was to process the S6-MF data with the minimum possible level of approximations along the processing pipeline but still maintaining a very efficient prototype from the computational point of view. For this scope, a novel and computationally efficient numerical retracking scheme with interface to the in-flight PTR (Point Target Response) provided by the instrument calibration chain has been put in place within S6PP for both the Low-Resolution and High-Resolution modes whereas the Delay-Doppler beam-forming is carried out by applying the range walk correction based on a computationally efficient algorithm (Chirp Zeta-Transform). The impact of the range walk correction and of the in-flight PTR interface is assessed for HRM and LRM, respectively. The paper shows that the proposed processing baseline ensures a dataset robust from the currently known instrumental degradation or ageing issues, both in LRM and HRM mode and, once this is done, that Sentinel-6 Michael Freilich global mean sea level measurement is in line with the one measured by Jason-3. [ABSTRACT FROM AUTHOR]

Over the past few decades, there has been a significant increase in the number of Earth observation satellites, and the area of ground targets requiring observation has also been expanding. To effectively utilize the capabilities of these satellites and capture larger areas of ground targets, it has become essential to plan imaging tasks for large regional coverage using multiple satellites. First, we establish a 0-1 integer programming model to accurately describe the problem and analyze the challenges associated with solving the model. Second, we propose a heuristic algorithm based on the triple grids method. This approach utilizes a generated grid to create fewer candidate strips, a calculation grid to determine the effective coverage area more accurately, and a refined grid to solve the issue of repeated coverage of strips. Furthermore, we employ an approximation algorithm to further improve the solutions obtained from the heuristic algorithm. By comparing the proposed method to the traditional greedy heuristic algorithm and three evolutionary algorithms, the results show that our method has better performance in terms of coverage and efficiency. [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]

This paper introduces the d-distanceb-matching problem, in which we are given a bipartite graph G = (S , T ; E) with S = { s 1 , ⋯ , s n } , a weight function on the edges, an integer d ∈ Z + and a degree bound function b : S ∪ T → Z + . The goal is to find a maximum-weight subset M ⊆ E of the edges satisfying the following two conditions: (1) the degree of each node v ∈ S ∪ T is at most b(v) in M, (2) if s i t , s j t ∈ M , then | i - j | ≥ d . In the cyclic version of the problem, the nodes in S are considered to be in cyclic order. We get back the (cyclic)d-distance matching problem when b (s) = 1 for s ∈ S and b (t) = ∞ for t ∈ T . We prove that the d-distance matching problem is APX-hard, even in the unweighted case. We show that 2 - 1 d is a tight upper bound on the integrality gap of the natural integer programming model for the cyclic d-distance b-matching problem provided that (2 d - 1) divides the size of S. For the non-cyclic case, the integrality gap is shown to be at most (2 - 2 d) . The proofs give approximation algorithms with guarantees matching these bounds, and also improve the best known algorithms for the (cyclic) d-distance matching problem. In a related problem, our goal is to find a permutation of S maximizing the weight of the optimal d-distance b-matching. This problem can be solved in polynomial time for the (cyclic) d-distance matching problem — even though the (cyclic) d-distance matching problem itself is NP-hard and also hard to approximate arbitrarily. For (cyclic) d-distance b-matchings, however, we prove that finding the best permutation is NP-hard, even if b ≡ 2 or d = 2 , and we give e-approximation algorithms. [ABSTRACT FROM AUTHOR]

This study addresses the energy efficiency challenge in cloud data centers by examining the Virtual Machine Placement (VMP) problem. VMP involves mapping virtual machines (VMs) to physical machines (PMs) under capacity constraints. The paper focuses on the bin packing with linear usage cost (BPLUC) variant of bin packing, which includes fixed and variable costs in the calculation of the cost of a used bin. We prove that every approximation algorithm for the bin and vector bin packing can be used for BPLUC and VBPLUC, respectively. We propose a more power-efficient approach to VMP by applying a vector bin packing algorithm to minimize power consumption in data centers. We test the proposed algorithm on various synthetic and real workloads, and the experimental results demonstrate that it is more power-efficient than existing algorithms for VMP. The findings suggest that the proposed algorithm has significant implications for energy-efficient strategies in cloud data centers. Generally, this study makes contributes to the development of energy-efficient approaches to VMP that can help reduce power consumption and improve the sustainability of cloud data centers. [ABSTRACT FROM AUTHOR]

We present combinatorial and parallelizable algorithms for the maximization of a submodular function, not necessarily monotone, with respect to a size constraint. We improve the best approximation factor achieved by an algorithm that has optimal adaptivity and nearly optimal query complexity to 1/6−ε, and even further to 0.193−ε by increasing the adaptivity by a factor of O(log(k)). The conference version of this work mistakenly employed a subroutine that does not work for non-monotone, submodular functions. In this version, we propose a fixed and improved subroutine to add a set with high average marginal gain, ThreshSeq, which returns a solution in O(log(n)) adaptive rounds with high probability. Moreover, we provide two approximation algorithms. The first has approximation ratio 1/6 − ε, adaptivity O(log(n)), and query complexity O(n log(k)), while the second has approximation ratio 0.193 − ε, adaptivity O(log(n) log(k)), and query complexity O(n log(k)). Our algorithms are empirically validated to use a low number of adaptive rounds and total queries while obtaining solutions with high objective value in comparison with state-of-the-art approximation algorithms, including continuous algorithms that use the multilinear extension. 1. [ABSTRACT FROM AUTHOR]

In this paper, we study restricted variations of the following obnoxious facility location problem in the plane: locate k new obnoxious facilities amidst n ordered demand points (existing facility sites) in the plane so that none of the existing facility sites are affected. We study this problem in two restricted settings. The obnoxious facilities are constrained to be centered on (i) a predetermined horizontal line segment pq ¯ , and (ii) the boundary arc of a predetermined disk C . For the problem in (i), we first give an (1 - ϵ) -approximation algorithm that runs in O (n + k) log | | p q | | 2 (k - 1) ϵ time, where ϵ > 0 and ||pq|| is the length of pq ¯ . We then propose two exact polynomial time algorithms, one based on doing binary search on all candidates and the other with the parametric search technique of Megiddo (J ACM 30:852–865, 1983); that will take O (n k) 2 time and O (n + k) 2 time respectively. Continuing further, using the improved parametric technique, we give an O (n log n) -time algorithm for k = 2 . We also show that the (1 - ϵ) -approximation algorithm of (i) can be easily adapted to solve the problem (ii) with an extra multiplicative factor of n in the running time. Finally, we give a O (n 3 k) -time dynamic programming solution to the min-sum obnoxious facility location problem restricted to a line segment where the demand points are associated with weights, and the goal is to minimize the sum of the weights of the points covered. [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]

Conceptual distance refers to the degree of proximity between two concepts within a conceptualization. It is closely related to semantic similarity and relationships, but its measurement strongly depends on the context of the given concepts. DIS-C represents an advancement in the computation of semantic similarity/relationships that is independent of the type of knowledge structure and semantic relations when generating a graph from a knowledge base (ontologies, semantic networks, and hierarchies, among others). This approach determines the semantic similarity between two indirectly connected concepts in an ontology by propagating local distances by applying an algorithm based on the All Pairs Shortest Path (APSP) problem. This process is implemented for each pair of concepts to establish the most effective and efficient paths to connect these concepts. The algorithm identifies the shortest path between concepts, which allows for an inference of the most relevant relationships between them. However, one of the critical issues with this process is computational complexity, combined with the design of APSP algorithms, such as Dijkstra, which is n 3 . This paper studies different alternatives to improve the DIS-C approach by adapting approximation algorithms, focusing on Dijkstra, pruned Dijkstra, and sketch-based methods, to compute the conceptual distance according to the need to scale DIS-C to analyze very large graphs; therefore, reducing the related computational complexity is critical. Tests were performed using different datasets to calculate the conceptual distance when using the original version of DIS-C and when using the influence area of nodes. In situations where time optimization is necessary for generating results, using the original DIS-C model is not the optimal method. Therefore, we propose a simplified version of DIS-C to calculate conceptual distances based on centrality estimation. The obtained results for the simple version of DIS-C indicated that the processing time decreased 2.381 times when compared to the original DIS-C version. Additionally, for both versions of DIS-C (normal and simple), the APSP algorithm decreased the computational cost when using a two-hop coverage-based approach. [ABSTRACT FROM AUTHOR]

The integrated industrial control systems require a reliable communication among each part of control systems. The limitation of network topology comprises the low latency of data transmission. The network algorithm topologies are sometimes failed to ensure the faulttolerant network design even if they offer it. Therefore, this works investigates a Node Insertion Algorithm (NIA) and Ant Colony Optimization (ACO) in order to solve the Travelling Salesman Problem (TSP) for network topologies in a communication network. The NP Non deterministic (polynomial time)-hardness based of TSP leads to the impossibility of polynomial time algorithm to solve an exponentially increasing amount of communication addresses. TSP itself is a well-known solution method known in the graph theory which is based on approximation algorithm. Therefore, this work also presents a comparison between the NIA and ACO for 200 nodes of network topologies. The results show that NIA is superior than ACO in terms of resulting ring's cost and computation duration. Three topologies are tested and it is observable that NIA requires only 14.88 seconds to finish the computation in which the resulting ring's length reaches 164019 units. Therefore, the achievement of the NIA can be applied for logical and physical nodes for a reliable connection in an industrial topology network. [ABSTRACT FROM AUTHOR]

Recently, networks have faced a significant challenge in terms of security due to constant unauthorized access by hackers, resulting in the compromise of network user data. To enhance network security, there are various approaches that can be employed, including the utilization of firewalls, encryption, and antivirus software. Among these methods, one type of system that can be implemented is an intrusion detection system (IDS), which actively monitors the network to identify any intrusions. In order to effectively detect any unauthorized or malicious activities, sophisticated techniques such as genetic algorithms, cuckoo searches, and FLAME are employed. This research proposes a novel IDS that aims to improve the detection of intrusions. The proposed IDS initially conducts feature filtration using fuzzy clustering through the local approximation of the membership algorithm (FLAME), which effectively reduces the number of features that need to be analyzed and processed. Subsequently, the system detects attacks by implementing an extended classifier system (XCS) that incorporates a genetic algorithm (GA) to enhance the accuracy of intrusion detection. By incorporating the cuckoo search and selection within GA, while considering different crossover and mutation probabilities, instead of solely relying on traditional GA, it is anticipated that intrusion detection accuracy will be improved. To evaluate the performance of the proposed IDS, it was tested on the KDD99 dataset and compared with several other IDSs that were also tested on the same dataset. The experimental results clearly indicate that the proposed IDS significantly enhances the detection rate (DR) and accuracy while also significantly reducing the false alarm rate (FAR) and these impressive results were 100%, 99.99% and 0.05% respectively. The performance comparisons reveal that, overall, the proposed IDS outperforms several existing IDSs in terms of intrusion detection performance. [ABSTRACT FROM AUTHOR]

We study the following scheduling problem with transportation. Given a set of n jobs that need to be processed on a single machine, we need to deliver the finished jobs to one of the two destinations using a single transporter. The goal is to minimize the time that all the jobs are delivered to their destination, such that the transporter returns. We propose a 11 / 6 + ε -approximation algorithm which improves upon the best-known approximation ratio of 2. [ABSTRACT FROM AUTHOR]

We consider batch scheduling on m machines to minimize the makespan. Each job has a given set of machines to be assigned. Each machine can process several jobs simultaneously as a batch, and the machines may have different batch capacities. We study two models: (i) scheduling on equal-speed batch machines under a nested processing set restriction, where the machines have the same processing speed, and (ii) scheduling on uniform batch machines under a tree-hierarchical processing set restriction, where the machines have different processing speeds. For both models we design polynomial-time approximation algorithms to solve them. The algorithms have a worst-case ratio of 2 for non-identical batch capacities and a worst-case ratio of 2 - 1 / m for identical batch capacities. [ABSTRACT FROM AUTHOR]

We study a generalization of the well-known traveling salesman problem in a metric space, in which each city is associated with a release time. The salesman has to visit each city at or after its release time. There exists a naive 5/2-approximation algorithm where the salesman simply starts to route the network after all cities are released. Interestingly, this bound has never been improved for more than two decades. In this paper, we revisit the problem and achieve the following results. First, we devise an approximation algorithm with performance ratio less than 5/2 when the number of distinct release times is fixed. Then, we analyze a natural class of algorithms and show that no performance ratio better than 5/2 is possible unless the Metric TSP can be approximated with a ratio strictly less than 3/2, which is a well-known longstanding open question. Finally, we consider a special case where the graph has a heavy edge and present an approximation algorithm with performance ratio less than 5/2. [ABSTRACT FROM AUTHOR]

We study several two-machine shop scheduling problems, namely flow shop, job shop and open shop scheduling problems under linear constraints. In these problems, the processing times of two stages of jobs are also decision variables and satisfy a system of linear constraints. The goal of each problem is to determine the processing time of each job, and to schedule the jobs to the shop machine such that the makespan, i.e., the completion time of all jobs, is minimized. These problems can find application in various areas, such as industrial production, advertising and automotive maintenance. We study the computational complexity and propose polynomial-time optimal or approximation algorithms for them. In particular, we show that although a two-machine flow shop scheduling problem and a two-machine job shop scheduling problem without recirculation can be solved in polynomial time, the problems where processing times satisfy linear constraints are generally NP-hard in the strong sense. Then, we design algorithms for various settings of these problems. We design polynomial-time algorithms for them when there are a fixed number of constraints. For the general case, we first propose a simple 2-approximation algorithm, and then design a polynomial-time approximation schemes. In contrast to the previous two problems, we show that the two-machine open shop scheduling problem under linear constraints can be solved in polynomial time. [ABSTRACT FROM AUTHOR]

This paper presents a QR decomposition based low-rank approximation algorithm for training and prediction in Gaussian process regression. Conventional low-rank methods like FITC, Nyström, etc., rely on low-rank approximations to the full kernel matrix that are derived from a set of representative data points. Training with FITC involves the selection of these representative points and is computationally intensive when the dimension of the dataset is large. Prediction accuracy of Nyström suffers when the number of representative points is small or when the length scale is small. The algorithm proposed here uses the thin QR decomposition of the low-rank matrix used in the Nyström approximation. We show that the marginal likelihood and its derivatives needed for training can be split into the subspace belonging to that approximation and its orthogonal complement. During prediction, we further restrict the target vectors into this subspace and thus eliminate the numerical error caused by very low noise variance. Use of the QR factorization improves the training and prediction performance. Experiments on real and synthetic data show that our approach is more accurate and faster than conventional methods. Our algorithm performs well at low length scales and achieves the prediction accuracy comparable to the full kernel matrix approach even for low rank approximations, without the need to optimize the representative points. This results in a simpler and faster approximation that could be used to scale Gaussian process regression to large datasets. [ABSTRACT FROM AUTHOR]

We present improved algorithms for the Steiner tree problem with the minimum number of Steiner points and bounded edge length. Given n terminal points in a 2D Euclidean plane and an edge length bound, the problem asks to construct a spanning tree of n terminal points with minimal Steiner points such that every edge length of the spanning tree is within the given bound. This problem is known to be NP-hard and has practical applications such as relay node placements in wireless networks, wavelength-division multiplexing(WDM) optimal network design, and VLSI design. The best-known deterministic approximation algorithm has O(n3) running time with an approximation ratio of 3. This paper proposes an efficient approximation algorithm using the Voronoi diagram that guarantees an approximation ratio of 3 in O(n log n) time. We also present the first exact algorithm to find an optimal Steiner tree for given three terminal points in constant time. Using this exact algorithm, we improve the 3-approximation algorithm with better performance regarding the number of required Steiner points in O(n log n) time. [ABSTRACT FROM AUTHOR]

Multi-h continuous phase modulation (CPM), with extremely high spectral efficiency, involves the plague of high demodulation complexity with a large number of matched filters and a complex trellis. In this paper, an efficient all-digital demodulator for multi-h continuous phase modulation (CPM) is proposed based on a low-complexity decision-directed synchronization algorithm. Based on the maximum-likelihood estimation of the carrier phase and timing errors, we propose a reduced-complexity timing error detector with linear phase approximation (LPA) to the phase of the multi-h CPM. Compared with the traditional synchronization methods, it avoids derivative matched filtering and reduces about 2/3 of matched filters. The estimated accuracy and bit error rate (BER) performance of the LPA-based synchronization algorithm have no loss, as shown by the numerical simulation. Its stability is verified by the derived S-curve. Then, the receivers with the LPA-based synchronization for the three kinds of promising multi-h CPM are implemented on a Xilinx Kintex-7 FPGA platform. The experimental results show that the onboard tested BER of the proposed design has an ignorable loss in the numerical simulation. The implementation overhead on FPGA is significantly reduced by about 27% slices, 64% DSPs, and 70% block RAMs compared with the conventional method. [ABSTRACT FROM AUTHOR]

Temporal graphs are graphs whose topology is subject to discrete changes over time. Given a static underlying graph G , a temporal graph is represented by assigning a set of integer time-labels to every edge e of G , indicating the discrete time steps at which e is active. We introduce and study the complexity of a natural temporal extension of the classical graph problem Maximum Matching , taking into account the dynamic nature of temporal graphs. In our problem, Maximum Temporal Matching , we are looking for the largest possible number of time-labeled edges (simply time-edges) (e , t) such that no vertex is matched more than once within any time window of Δ consecutive time slots, where Δ ∈ N is given. We prove strong computational hardness results for Maximum Temporal Matching , even for elementary cases, as well as fixed-parameter algorithms with respect to natural parameters and polynomial-time approximation algorithms. [ABSTRACT FROM AUTHOR]

We consider the max hypergraph 3-cut problem with limited unbalance (MH3C-LU). The objective is to divide the vertex set of an edge-weighted hypergraph H = (V , E , w) into three disjoint subsets V 1 , V 2 , and V 3 such that the sum of edge weights cross different parts is maximized subject to | | V i | - | V l | | ≤ B ( ∀ i ≠ l ∈ { 1 , 2 , 3 } ) for a given parameter B. This problem is NP-hard because it includes some well-known problems like the max 3-section problem and the max 3-cut problem as special cases. We formulate the MH3C-LU as a ternary quadratic program and present a randomized approximation algorithm based on the complex semidefinite programming relaxation technique. [ABSTRACT FROM AUTHOR]

In this paper, we propose and investigate the individually fair k-center with outliers (IFkCO). In the IFkCO, we are given an n-sized vertex set in a metric space, as well as integers k and q. At most k vertices can be selected as the centers and at most q vertices can be selected as the outliers. The centers are selected to serve all the not-an-outlier (i.e., served) vertices. The so-called individual fairness constraint restricts that every served vertex must have a selected center not too far way. More precisely, it is supposed that there exists at least one center among its ⌈ (n - q) / k ⌉ closest neighbors for every served vertex. Because every center serves (n - q) / k vertices on the average. The objective is to select centers and outliers, assign every served vertex to some center, such that the maximum fairness ratio over all served vertices is minimized, where the fairness ratio of a vertex is defined as the ratio between its distance with the assigned center and its distance with a ⌈ (n - q) / k ⌉ th closest neighbor. As our main contribution, a 4-approximation algorithm is presented, based on which we develop an improved algorithm from a practical perspective. Extensive experiment results on both synthetic datasets and real-world datasets are presented to illustrate the effectiveness of the proposed algorithms. [ABSTRACT FROM AUTHOR]

Matrix decomposition is a widely used tool in machine learning with many applications such as dimension reduction or visualization. In this paper we consider decomposing X, a matrix of size n × m , to a product WS where we require that S, a matrix of size n × k , needs to have consecutive ones property. More specifically, we require that each row of S needs to be in the form of 0 , ... , 0 , 1 , ... , 1 , 0 , ... , 0 . Such decompositions are particularly meaningful if X is a matrix where each row represents a time series; in such a case the ones in each row in S represent a time segment. We show that the optimization problem is inapproximable. To solve the problem we propose 5 different algorithms. The first two algorithms are based on solving iteratively S while keeping W fixed and then solving W while keeping S fixed. The next two algorithms are based on greedily optimizing a single row in S and the corresponding column in W. The last algorithm first finds the optimal decomposition of with 2 k - 1 non-overlapping rows, and then greedily combines the rows until k rows remain. We compare the algorithms experimentally, focusing on the quality of the decomposition as well as the computational time. We show experimentally that our algorithms yield interpretable results in practical time. [ABSTRACT FROM AUTHOR]

The goal of this paper is to find a stabilizing and optimal control policy for a class of systems dictated by Euler–Lagrange dynamics, that also satisfies predetermined response criteria. The proposed methodology builds upon two stages. Initially, a neural network is trained online via an iterative process to capture the system dynamics, which are assumed to be unknown. Subsequently, a successive approximation algorithm is applied, employing the acquired dynamics from the previous step, to find a near-optimal control law that takes into consideration prescribed performance specifications, such as convergence speed and steady-state error. In addition, we concurrently guarantee that the system evolves exclusively within the compact set for which sufficient approximation capabilities have been acquired. Finally, we validate our claims through various simulated studies that confirm the success of both the identification process and the minimization of the cost function. [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]

We study the investment incentives created by truthful mechanisms that allocate resources using approximation algorithms. Some approximation algorithms guarantee nearly 100% of the optimal welfare in the allocation problem but guarantee nothing when accounting for investment incentives. An algorithm's allocative and investment guarantees coincide if and only if its confirming negative externalities are sufficiently small. We introduce fast approximation algorithms for the knapsack problem that have no confirming negative externalities and guarantees close to 100% for both allocation and investment. [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]

The identifying code problem for a given graph involves finding a minimum subset of vertices such that each vertex of the graph is uniquely specified by its nonempty neighborhood within the identifying code. The combinatorial optimization problem has a wide variety of applications in location and detection schemes. Finding an identifying code of minimum possible size is a difficult task. In fact, it has been proven to be computationally intractable (NP-complete). Therefore, the use of heuristics to provide good approximations in a reasonable amount of time is justified. In this work, we present a new population-based local search algorithm for finding identifying codes of minimum cost. Computational experiments show that the proposed approach was found to be more effective than other state-of-the-art algorithms at generating high-quality solutions in different types of graphs with varying numbers of vertices. [ABSTRACT FROM AUTHOR]

In this research, we investigate Hilfer-type FDDEs of both linear and nonlinear nature, with orders α and β. We studied some Riemann-Liouville, Caputo-Liouville, and Hilfer fractional derivatives properties; and then used them to convert our fractional delay problem into an equivalent fractional Volterra delay problem. After that, for the resulting fractional Volterra delay problem, using the CMT, existence-uniqueness is demonstrated. For numerical solutions, we studied the orthogonal shifted Legendre polynomials and used them as the basis for the Galerkin algorithm to find an approximation solution to the corresponding FDDE. By employing this algorithm, the provided FDDE is converted into a series of algebraic systems. By solving this system, the approximated solutions for the equation are obtained. The main algorithm advantage is that the number of needed iterations is low compared with the soft gained results. Some linear and nonlinear numerical applications together with several figures and tables are utilized to prove the performance and accuracy of the algorithm. The outcomes results are considered according to the given analysis and the numerical method was offered in the last section with several hints to guide future work. [ABSTRACT FROM AUTHOR]

In this paper, we propose a monocular catadioptric panoramic depth estimation algorithm based on an improved end-to-end neural network model. First, we use an enhanced concentric circle approximation unfolding algorithm to unfold the panoramic images captured by the catadioptric panoramic camera and then extract the e [ABSTRACT FROM AUTHOR]

This paper presents a combined method for the equivalent circuit parameters estimation of cage induction motors. The method is based on dual usage of the particle swarm optimization algorithm and the approximation of rotor parameters as a function of the speed, due to the influence of the skin effect. The approximation of rotor parameters as a function of the speed is not directly applied in the parameters estimation algorithm, but it is used to obtain the torque-speed characteristics of cage induction motors. The first stage of the optimization includes the estimation of equivalent circuit parameters of a motor for the nominal operating mode, while the rotor parameters at the start of the motor are estimated in the second stage of the optimization. These parameters are obtained as a result of minimizing the error between the calculated and the manufacture data. The proposed method is applied on eight two-pole induction motors with different rated powers, energy efficiency class IE3, manufactured by ABB. The results are verified by comparing the obtained torque-speed characteristics with the corresponding characteristics provided by the manufacturer (i.e., ABB) using the MotSize program. It is shown that the torque-speed characteristics obtained by the proposed method are in a good agreement with the characteristics given by the manufacturer. Also, the value of the mean absolute relative error does not exceed 5% for all considered motors. [ABSTRACT FROM AUTHOR]