Search

The advancement of autonomous capabilities in maritime navigation has gained significant attention, with a trajectory moving from decision support systems to full autonomy. This push towards autonomy has led to extensive research focusing on collision avoidance, a critical aspect of safe navigation. Among the various possible approaches, dynamic programming is a promising tool for optimizing collision avoidance maneuvers. This paper presents a DP formulation for the collision avoidance of autonomous vessels. We set up the problem framework, formulate it as a multi-stage decision process, define cost functions and constraints focusing on the actual requirements a marine maneuver must comply with, and propose a solution algorithm leveraging parallel computing. Additionally, we present a greedy approximation to reduce algorithm complexity. We put the proposed algorithms to the test in realistic navigation scenarios and also develop an extensive test on a large set of randomly generated scenarios, comparing them with the RRT* algorithm using performance metrics proposed in the literature. The results show the potential benefits of an autonomous navigation or decision support framework. [ABSTRACT FROM AUTHOR]

Many modern day cloud hosted applications such as virtual reality, real time games require low latency data access and computation to improve response time. So it is essential to bring the computation and data storage edge servers closer to the user's geographical location to improve response times and save bandwidth. In particulars, in online gaming and on demand video services, the required application data present at cloud servers need to be placed on the edge servers to provide low latency app-functionalities. The transfer of huge amount of data from cloud server to edge server incurs high cost and time penalties. Thus, we need an efficient way to solve edge data distribution (EDD) problem which distribute the application data to the edge servers that minimizes transfer cost. In this work, we provide a refined formulation of an optimal approach to solve the EDD problem using integer linear programming (ILP) technique. Due to the time complexity limitation of the ILP approach, we propose an O(k) approximation algorithm based on network Steiner tree estimation (EDD-NSTE) for estimating solutions to dense large-scale EDD problem. The proposed approach is analyzed to be 11/6 approximation which is better than the state-of-the-art 2 approximation EDD-A approach. The experimental evaluation through simulation using real world EUA data set demonstrate that the EDD-NSTE outperform state-of-the-art approach and other representative approaches. [ABSTRACT FROM AUTHOR]

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

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.

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]

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]

We devise the first constant-factor approximation algorithm for finding an integral multi-commodity flow of maximum total value for instances where the supply graph together with the demand edges can be embedded on an orientable surface of bounded genus. This extends recent results for planar instances. Our techniques include an uncrossing algorithm, which is significantly more difficult than in the planar case, a partition of the cycles in the support of an LP solution into free homotopy classes, and a new rounding procedure for freely homotopic non-separating cycles. [ABSTRACT FROM AUTHOR]

The gate-based model is one of the leading quantum computing paradigms for representing quantum circuits. Within this paradigm, a quantum algorithm is expressed in terms of a set of quantum gates that are executed on the quantum hardware over time, subject to a number of constraints whose satisfaction must be guaranteed before running the circuit, to allow for feasible execution. The need to guarantee the previous feasibility condition gives rise to the Quantum Circuit Compilation Problem (QCCP). The QCCP has been demonstrated to be NP-Complete, and can be considered as a Planning and Scheduling problem. In this paper, we consider quantum compilation instances deriving from the general Quantum Approximation Optimization Algorithm (QAOA), applied to the MaxCut problem, devised to be executed on Noisy Intermediate Scale Quantum (NISQ) hardware architectures. More specifically, in addition to the basic QCCP version, we also tackle other variants of the same problem such as the QCCP-X (QCCP with crosstalk constraints), the QCCP-V (QCCP with variable qubit state initialization), as well as the QCCP-VX that includes both previous variants. All problem variants are solved using genetic algorithms. We perform an experimental study across a conventional set of instances taken from the literature, and show that the proposed genetic algorithm, termed G A VX , outperforms previous approaches in the literature. [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]

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]

Motivated by the soaking process under separate heating mode in iron and steel enterprises, we study the parallel batch machine scheduling problem with incompatible deteriorating jobs. The objective is to minimize makespan. A soaking furnace can be seen as a parallel batch processing machine. In order to avoid the thermal stress caused by excessive temperature difference, initial temperature is needed for the ingot before processing. With the increasing of waiting time, the ingot temperature decreases and the soaking time increases. This property is called deterioration. Setup time is needed between incompatible jobs. We show that if jobs have the same sizes, an optimal solution can be found within O(nlogn) time. If jobs have identical processing times, the problem is proved to be NP-hard in the strong sense. We propose an approximate algorithm whose absolute and asymptotic worst-case ratios are less than 2 and 11/9, respectively. When the jobs have arbitrary sizes and arbitrary processing times, the model is also NP-hard in the strong sense. An approximate algorithm with an absolute and asymptotic worst-case ratio less than 2 is proposed. The time complexity is O(nlogn). [ABSTRACT FROM AUTHOR]

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

How can we efficiently find very large numbers of clusters C in very large datasets N of potentially high dimensionality D? Here we address the question by using a novel variational approach to optimize Gaussian mixture models (GMMs) with diagonal covariance matrices. The variational method approximates expectation maximization (EM) by applying truncated posteriors as variational distributions and partial E-steps in combination with coresets. Run time complexity to optimize the clustering objective then reduces from O(NCD) per conventional EM iteration to O(N′G2D) for a variational EM iteration on coresets (with coreset size N ′ ≤ N and truncation parameter G ≪ C). Based on the strongly reduced run time complexity per iteration, which scales sublinearly with NC, we then provide a concrete, practically applicable, parallelized and highly efficient clustering algorithm. In numerical experiments on standard large-scale benchmarks we (A) show that also overall clustering times scale sublinearly with NC, and (B) observe substantial wall-clock speedups compared to already highly efficient recently reported results. The algorithm’s sublinear scaling allows for applications at scales where alternative methods cease to be applicable. We demonstrate such very large-scale applicability using the YFCC100M benchmark, for which we realize with a GMM of up to 50.000 clusters an optimization of a data density model with up to 150 M parameters. [ABSTRACT FROM AUTHOR]

Adversarial attacks have been extensively studied in recent years since they can identify the vulnerability of deep learning models before deployed. In this paper, we consider the black-box adversarial setting, where the adversary needs to craft adversarial examples without access to the gradients of a target model. Previous methods attempted to approximate the true gradient either by using the transfer gradient of a surrogate white-box model or based on the feedback of model queries. However, the existing methods inevitably suffer from low attack success rates or poor query efficiency since it is difficult to estimate the gradient in a high-dimensional input space with limited information. To address these problems and improve black-box attacks, we propose two prior-guided random gradient-free (PRGF) algorithms based on biased sampling and gradient averaging, respectively. Our methods can take the advantage of a transfer-based prior given by the gradient of a surrogate model and the query information simultaneously. Through theoretical analyses, the transfer-based prior is appropriately integrated with model queries by an optimal coefficient in each method. Extensive experiments demonstrate that, in comparison with the alternative state-of-the-arts, both of our methods require much fewer queries to attack black-box models with higher success rates. [ABSTRACT FROM AUTHOR]

This article presents a rough-to-fine evolutionary multiobjective optimization algorithm based on the decomposition for solving problems in which the solutions are initially far from the Pareto-optimal set. Subsequently, a tree is constructed by a modified $k$ -means algorithm on $N$ uniform weight vectors, and each node of the tree contains a weight vector. Each node is associated with a subproblem with the help of its weight vector. Consequently, a subproblem tree can be established. It is easy to find that the descendant subproblems are refinements of their ancestor subproblems. The proposed algorithm approaches the Pareto front (PF) by solving a few subproblems in the first few levels to obtain a rough PF and gradually refining the PF by involving the subproblems level-by-level. This strategy is highly favorable for solving problems in which the solutions are initially far from the Pareto set. Moreover, the proposed algorithm has lower time complexity. Theoretical analysis shows the complexity of dealing with a new candidate solution is $\mathcal {O}(M \log N)$ , where $M$ is the number of objectives. Empirical studies demonstrate the efficacy of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Although cell-free massive multiple-input–multiple-output (mMIMO) Internet-of-Things (IoT) systems can improve spectral efficiency (SE) significantly compared with conventional cellular mMIMO IoT systems due to high coverage and no intercell interference, the pilot contamination and active sensors (ASs) interference can still seriously limit the further improvement of SE. In this article, we first develop a model of the cell-free mMIMO IoT system and then derive a mathematical expression of the SE to formulate a maximized sum SE optimization problem for jointly controlling pilot and data power. This problem is nonconvex; thus, a successive convex approximation (SCA) iteration algorithm is proposed, which, in fact, approximates the objective and constraint function in each iteration, and converts the initial optimization problem into an easy-to-solve geometric programming (GP) problem. Finally, simulation results show that our proposed algorithm outperforms the existing algorithms related to power control optimization in terms of the sum SE performance. [ABSTRACT FROM AUTHOR]

This paper revisits the temporal difference (TD) learning algorithm for the policy evaluation tasks in reinforcement learning. Typically, the performance of TD(0) and TD($\lambda$ λ ) is very sensitive to the choice of stepsizes. Oftentimes, TD(0) suffers from slow convergence. Motivated by the tight link between the TD(0) learning algorithm and the stochastic gradient methods, we develop a provably convergent adaptive projected variant of the TD(0) learning algorithm with linear function approximation that we term AdaTD(0). In contrast to the TD(0), AdaTD(0) is robust or less sensitive to the choice of stepsizes. Analytically, we establish that to reach an $\epsilon$ ε accuracy, the number of iterations needed is $\tilde{O}(\epsilon ^{-2}\ln ^4\frac{1}{\epsilon }/\ln ^4\frac{1}{\rho })$ O ˜ (ε - 2 ln 4 1 ε / ln 4 1 ρ) in the general case, where $\rho$ ρ represents the speed of the underlying Markov chain converges to the stationary distribution. This implies that the iteration complexity of AdaTD(0) is no worse than that of TD(0) in the worst case. When the stochastic semi-gradients are sparse, we provide theoretical acceleration of AdaTD(0). Going beyond TD(0), we develop an adaptive variant of TD($\lambda$ λ ), which is referred to as AdaTD($\lambda$ λ ). Empirically, we evaluate the performance of AdaTD(0) and AdaTD($\lambda$ λ ) on several standard reinforcement learning tasks, which demonstrate the effectiveness of our new approaches. [ABSTRACT FROM AUTHOR]

Multi-relational learning on knowledge graphs infers high-order relations among the entities across the graphs. This learning task can be solved by label propagation on the tensor product of the knowledge graphs to learn the high-order relations as a tensor. In this paper, we generalize a widely used label propagation model to the normalized tensor product graph, and propose an optimization formulation and the scalable Low-rank Tensor-based Label Propagation algorithm (LowrankTLP) to infer multi-relations for two learning tasks, hyperlink prediction and multiple graph alignment. The optimization formulation minimizes the upper bound of the noisy-tensor estimating error for multiple graph alignment, by learning with a subset of the eigen-pairs in the spectrum of the normalized tensor product graph. We also provide a data-dependent transductive Rademacher bound for binary hyperlink prediction. We accelerate LowrankTLP with parallel tensor computation which enables label propagation on a tensor product of 100 graphs each of size 1000 in less than half hour in the simulation. LowrankTLP was also applied to predicting the author-paper-venue hyperlinks in publication records, alignment of segmented regions across up to 26 CT-scan images and alignment of protein-protein interaction networks across multiple species. The experiments demonstrate that LowrankTLP indeed well approximates the original label propagation with better scalability and accuracy. [ABSTRACT FROM AUTHOR]

One of the most extensively studied combinatorial optimization problems is the Travelling Salesman Problem (TSP). Considerable research efforts in the past have resulted in exact solvers. However, the runtime of such hand-crafted solutions increases exponentially with problem size. Ising model based solvers have also gained prominence due to their abilities to find fast and approximate solutions for combinatorial optimization problems. However, such Ising based heuristics also suffer from scalability as the solution quality becomes increasingly sub-optimal with increase in problem size. In this work, we propose Neuro-Ising – a machine learning framework which uses Ising models to find clusters of near-optimal partial solutions of large scale TSPs and combines those solutions by employing a supervised data driven mechanism, which we model as a Graph Neural Network (GNN). The GNN is trained from solution instances obtained through exact solvers and hence, the proposed approach generalizes to unseen problems while avoiding the run-time complexity otherwise required, if the solution is built from scratch. Using standard computing resources, our proposed framework rapidly converges to near-optimal solutions for 15 TSPs (upto $\sim 5k$ cities) from the TSPLib benchmark suite. We report $\sim 10.66\times $ speedup over Tabu Search for 8 problems. Furthermore, compared to two state-of-the-art clustering-based TSP solvers, Neuro-Ising achieves $\sim 38 \times $ faster convergence along with $\sim 8.9\%$ better quality of solution, on average. [ABSTRACT FROM AUTHOR]

Owing to its good compression ability, discrete cosine transform (DCT) is widely used in signal processing, including high-efficiency video coding (HEVC). For efficient implementation, approximate DCTs and integer DCTs were proposed, but the challenge in the tradeoff between coding performance and implementation cost always exists. To solve this problem, this article proposes a new algorithm to derive Int-DCT with good coding performance and low hardware cost. To address the multiobjective optimization problem, we extract information from the initially shortlisted transform matrices to derive the weighting factors for the different matrices properties. Those properties having a higher impact to the performance are assigned with higher weights and vice versa. Subsequently, an efficient search algorithm is proposed to shortlist those candidates which can lead to better coding performance evaluated by the proposed measure. Last but not the least, a splitting method is proposed to search the efficient extended double-base number system (EDBNS) representation of the coefficients for hardware implementation and select the solution which encounters the lowest cost. The experimental results in ASIC demonstrate that the implementation area and power cost of designs by the new algorithm are reduced by at least 11.1% and 17.5% for 32-point transform, respectively, over other competing algorithms. Meanwhile, the transforms generated by the proposed algorithm causes negligible impact to coding performance compared to the original transforms in HEVC. [ABSTRACT FROM AUTHOR]

This article deals with nonconvex stochastic optimization problems in deep learning. Appropriate learning rates, based on theory, for adaptive-learning-rate optimization algorithms (e.g., Adam and AMSGrad) to approximate the stationary points of such problems are provided. These rates are shown to allow faster convergence than previously reported for these algorithms. Specifically, the algorithms are examined in numerical experiments on text and image classification and are shown in experiments to perform better with constant learning rates than algorithms using diminishing learning rates. [ABSTRACT FROM AUTHOR]

This article introduces a new deep learning approach to approximately solve the covering salesman problem (CSP). In this approach, given the city locations of a CSP as input, a deep neural network model is designed to directly output the solution. It is trained using the deep reinforcement learning without supervision. Specifically, in the model, we apply the multihead attention (MHA) to capture the structural patterns, and design a dynamic embedding to handle the dynamic patterns of the problem. Once the model is trained, it can generalize to various types of CSP tasks (different sizes and topologies) without the need of retraining. Through controlled experiments, the proposed approach shows desirable time complexity: it runs more than 20 times faster than the traditional heuristic solvers with a tiny gap of optimality. Moreover, it significantly outperforms the current state-of-the-art deep learning approaches for combinatorial optimization in the aspect of both training and inference. In comparison with traditional solvers, this approach is highly desirable for most of the challenging tasks in practice that are usually large scale and require quick decisions. [ABSTRACT FROM AUTHOR]

Automated hyperparameter optimization (HPO) has gained great popularity and is an important component of most automated machine learning frameworks. However, the process of designing HPO algorithms is still an unsystematic and manual process: new algorithms are often built on top of prior work, where limitations are identified and improvements are proposed. Even though this approach is guided by expert knowledge, it is still somewhat arbitrary. The process rarely allows for gaining a holistic understanding of which algorithmic components drive performance and carries the risk of overlooking good algorithmic design choices. We present a principled approach to automated benchmark-driven algorithm design applied to multifidelity HPO (MF-HPO). First, we formalize a rich space of MF-HPO candidates that includes, but is not limited to, common existing HPO algorithms and then present a configurable framework covering this space. To find the best candidate automatically and systematically, we follow a programming-by-optimization approach and search over the space of algorithm candidates via Bayesian optimization. We challenge whether the found design choices are necessary or could be replaced by more naive and simpler ones by performing an ablation analysis. We observe that using a relatively simple configuration (in some ways, simpler than established methods) performs very well as long as some critical configuration parameters are set to the right value. [ABSTRACT FROM AUTHOR]

In healthcare management, one important problem is how to efficiently allocate resources with limited capacities. From the point of view of a central decision maker with a long planning horizon, many healthcare resources such as appointment slots, operation rooms, and hospital beds can be regarded as reusable resources. Motivated by this observation, we study a new version of the assignment problem of reusable resources to sequentially arriving users. Different from previous works on reusable resources, we assume that each user will tell us the intended usage duration of each resource upfront before a decision needs to be made. In the setting where users arrive randomly according to a certain distribution, we propose an algorithm based on linear approximations of the optimal value functions, and show that it performs better than common methods developed for the case where usage times are known upon return in different simulations, as well as in a case study with real data. When users arrive in an adversarial order, we show by example that it is hard to design an algorithm with a lower-bounded competitive ratio. As users are much less likely to arrive in an adversarial order in reality, our proposed algorithm can be used to effectively schedule resources such as appointment slots and operation rooms in hospitals. [ABSTRACT FROM AUTHOR]

We present a new framework for solving optimization problems with a diseconomy of scale. In such problems, our goal is to minimize the cost of resources used to perform a certain task. The cost of resources grows superlinearly, as xq, q≥ 1, with the amount x of resources used. We define a novel linear programming relaxation for such problems and then show that the integrality gap of the relaxation is Aq, where Aq is the q-th moment of the Poisson random variable with parameter 1. Using our framework, we obtain approximation algorithms for the Minimum Energy Efficient Routing, Minimum Degree Balanced Spanning Tree, Load Balancing on Unrelated Parallel Machines, and Unrelated Parallel Machine Scheduling with Nonlinear Functions of Completion Times problems. Our analysis relies on the decoupling inequality for nonnegative random variables. The inequality states that ║∑i=1nXi║q ≤ Cq║∑i=1nYi║q, where Xi are independent nonnegative random variables, Yi are possibly dependent nonnegative random variables, and each Yi has the same distribution as Xi. The inequality was proved by de la Peña in 1990. De la Peña, Ibragimov, and Sharakhmetov showed that Cq≤ 2 for q∈(1,2) and Cq≤ Aq1/q for q≥ 2. We show that the optimal constant is Cq= Aq1/q for any q≥ 1. We then prove a more general inequality: For every convex function ϕ, E[ϕ(∑i=1nXi)] ≤ E[ϕ (P∑i=1n Yi)], and, for every concave function ψ, E[ψ (∑i=1n Xi)] ≥ E[ψ(P∑i=1n Yi)], where P is a Poisson random variable with parameter 1 independent of the random variables Yi. [ABSTRACT FROM AUTHOR]

In a large cloud data center HPC system, a critical problem is how to allocate the submitted tasks to heterogeneous servers that will achieve the goal of maximizing the system’s gain defined as the value of completed tasks minus system operation costs. We consider this problem in the online setting that tasks arrive in batches and propose a novel deep reinforcement learning (DRL) enhanced greedy optimization algorithm of two-stage scheduling interacting task sequencing and task allocation. For task sequencing, we deploy a DRL module to predict the best allocation sequence for each arriving batch of tasks based on the knowledge (allocation strategies) learnt from previous batches. For task allocation, we propose a greedy strategy that allocates tasks to servers one by one online following the allocation sequence to maximize the total gain increase. We show that our greedy strategy has a performance guarantee of competitive ratio $\frac{1}{1+\kappa }$ 1 1 + κ to the optimal offline solution, which improves the existing result for the same problem, where $\kappa$ κ is upper bounded by the maximum cost-to-gain ratio of each task. While our DRL module enhances the greedy algorithm by providing the likely-optimal allocation sequence for each batch of arriving tasks, our greedy strategy bounds DRL’s prediction error within a proven worst-case performance guarantee for any allocation sequence. It enables a better solution quality than that obtainable from both DRL and greedy optimization alone. Extensive experiment evaluation results in both simulation and real application environments demonstrate the effectiveness and efficiency of our proposed algorithm. Compared with the state-of-the-art baselines, our algorithm increases the system gain by about 10% to 30%. Our algorithm provides an interesting example of combining machine learning (ML) and greedy optimization techniques to improve ML-based solutions with a worst-case performance guarantee for solving hard optimization problems. [ABSTRACT FROM AUTHOR]

This brief addresses the problem of implementing very large constant multiplications by a single variable under the shift-adds architecture using a minimum number of adders/subtractors. Due to the intrinsic complexity of the problem, we introduce an approximate algorithm, called TÕLL, which partitions the very large constants into smaller ones. To reduce the number of operations, TÕLL incorporates graph-based and common subexpression elimination methods proposed for the shift-adds design of constant multiplications. It can also consider the delay of a multiplierless design defined in terms of the maximum number of operations in series, i.e., the number of adder-steps, while reducing the number of operations. High-level experimental results show that the adder-steps of a shift-adds design can be reduced significantly with a little overhead in the number of operations. Gate-level experimental results indicate that while the shift-adds design can lead to a 36.6% reduction in gate-level area with respect to a design using a multiplier, the delay-aware optimization can yield a 48.3% reduction in minimum achievable delay of the shift-adds design when compared to the area-aware optimization. [ABSTRACT FROM AUTHOR]

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

Convolutional transform learning (CTL), learning filters by minimizing the data fidelity loss function in an unsupervised way, is becoming very pervasive, resulting from keeping the best of both worlds: the benefit of unsupervised learning and the success of the convolutional neural network. There have been growing interests in developing efficient CTL algorithms. However, developing a convergent and accelerated CTL algorithm with accurate representations simultaneously with proper sparsity is an open problem. This article presents a new CTL framework with a $log$ regularizer that can not only obtain accurate representations but also yield strong sparsity. To efficiently address our nonconvex composite optimization, we propose to employ the proximal difference of the convex algorithm (PDCA) which relies on decomposing the nonconvex regularizer into the difference of two convex parts and then optimizes the convex subproblems. Furthermore, we introduce the extrapolation technology to accelerate the algorithm, leading to a fast and efficient CTL algorithm. In particular, we provide a rigorous convergence analysis for the proposed algorithm under the accelerated PDCA. The experimental results demonstrate that the proposed algorithm can converge more stably to desirable solutions with lower approximation error and simultaneously with stronger sparsity and, thus, learn filters efficiently. Meanwhile, the convergence speed is faster than the existing CTL algorithms. [ABSTRACT FROM AUTHOR]

Bilevel optimization involves two levels of optimization, where one optimization problem is nested within the other. The structure of the problem often requires solving a large number of inner optimization problems that make these kinds of optimization problems expensive to solve. The reaction set mapping and the lower level optimal value function mapping are often used to reduce bilevel optimization problems to a single level; however, the mappings are not known a priori, and the need is to be estimated. Though there exist a few studies that rely on the estimation of these mappings, they are often applied to problems where one of these mappings has a known form, that is, piecewise linear, convex, etc. In this article, we utilize both these mappings together to solve general bilevel optimization problems without any assumptions on the structure of these mappings. Kriging approximations are created during the generations of an evolutionary algorithm, where the population members serve as the samples for creating the approximations. One of the important features of the proposed algorithm is the creation of an auxiliary optimization problem using the Kriging-based metamodel of the lower level optimal value function that solves an approximate relaxation of the bilevel optimization problem. The auxiliary problem when used for local search is able to accelerate the evolutionary algorithm toward the bilevel optimal solution. We perform experiments on two sets of test problems and a problem from the domain of control theory. Our experiments suggest that the approach is quite promising and can lead to substantial savings when solving bilevel optimization problems. The approach is able to outperform state-of-the-art methods that are available for solving bilevel problems, in particular, the savings in function evaluations for the lower level problem are substantial with the proposed approach. [ABSTRACT FROM AUTHOR]

By employing time-varying proximal functions, adaptive subgradient methods (ADAGRAD) have improved the regret bound and been widely used in online learning and optimization. However, ADAGRAD with full matrix proximal functions (ADA-FULL) cannot handle large-scale problems due to the impractical $O(d^3)$ O (d 3) time and $O(d^2)$ O (d 2) space complexities, though it has better performance when gradients are correlated. In this paper, we propose two efficient variants of ADA-FULL via a matrix sketching technique called frequent directions (FD). The first variant named as ADA-FD directly utilizes FD to maintain and manipulate low-rank matrices, which reduces the space and time complexities to $O(\tau d)$ O (τ d) and $O(\tau ^2d)$ O (τ 2 d) respectively, where $d$ d is the dimensionality and $\tau \ll d$ τ ≪ d is the sketching size. The second variant named as ADA-FFD further adopts a doubling trick to accelerate FD used in ADA-FD, which reduces the average time complexity to $O(\tau d)$ O (τ d) while only doubles the space complexity of ADA-FD. Theoretical analysis reveals that the regret of ADA-FD and ADA-FFD is close to that of ADA-FULL as long as the outer product matrix of gradients is approximately low-rank. Experimental results demonstrate the efficiency and effectiveness of our algorithms. [ABSTRACT FROM AUTHOR]

This article investigates the finite-time distributed approximate optimization problem of higher order multiagent systems, where the local cost functions are considered to be quadratic functions. This problem is solved via penalty-function-based method. First, by the penalty-function method, a global approximate cost function is constructed. Second, nonlinear distributed optimization algorithms are proposed for higher order multiagent systems by the tool of adding a power integrator technique. In the optimization algorithms design, the gradients of the approximate cost function are utilized. Under the proposed optimization algorithms, the agents approach the approximate optimal solution in finite time. Although there exist errors (they may be called approximation errors) between the approximate minimizers and the global accurate minimizer, the approximation errors can be regulated by penalty parameter and the relationship between the bound of the approximation errors and the penalty parameter is given explicitly. Furthermore, the proposed distributed approximate optimization algorithms are applied to the optimal rendezvous problem of wheeled multimobile robots, making the mobile robots achieve approximate optimization rendezvous in finite time. The effectiveness of the proposed distributed optimization algorithms and their applications to optimal rendezvous problem are validated by simulations. [ABSTRACT FROM AUTHOR]

Fog networks facilitate ultra-low latency through the use of data availability near the network edge in fog servers. Existing work in fog networks considers the objective of energy efficiency and low latency for internet-of-things (IoT) for resource allocation. These works provide solutions to energy efficiency and low latency resource allocation problem without consideration of secure communication. This article investigates the benefits of fog architecture from the perspective of three promising technologies namely device-to-device (D2D) communication, caching, and physical layer security. We propose security provisioning followed by mode selection for D2D-assisted fog networks. The secrecy rate maximization problem is formulated first, which belongs to mixed-integer nonlinear programming (MINLP) problem. It is NP-hard, that is why an exhaustive search for finding the solution is complex. Keeping in view the complexity, a nonlinear technique namely outer approximation algorithm (OAA) is applied. OAA is a traditional algorithm, whose results are compared with the proposed heuristic algorithm, namely the security heuristic algorithm (SHA). Performance of the network is observed for the different numbers of eavesdroppers, IoT nodes, and fog nodes. [ABSTRACT FROM AUTHOR]

In this article, we discuss a sequential algorithm for the computation of a minimum-time speed profile over a given path, under velocity, acceleration, and jerk constraints. Such a problem arises in industrial contexts, such as automated warehouses, where LGVs need to perform assigned tasks as fast as possible in order to increase productivity. It can be reformulated as an optimization problem with a convex objective function, linear velocity and acceleration constraints, and nonconvex jerk constraints, which, thus, represent the main source of the difficulty. While existing nonlinear programming (NLP) solvers can be employed for the solution of this problem, it turns out that the performance and robustness of such solvers can be enhanced by the sequential line-search algorithm proposed in this article. At each iteration, a feasible direction, with respect to the current feasible solution, is computed, and a step along such direction is taken in order to compute the next iterate. The computation of the feasible direction is based on the solution of a linearized version of the problem, and the solution of the linearized problem, through an approach that strongly exploits its special structure, represents the main contribution of this work. The efficiency of the proposed approach with respect to existing NLP solvers is proven through different computational experiments. Note to Practitioners—This article was motivated by the needs of LGV manufacturers. In particular, it presents an algorithm for computing the minimum-time speed law for an LGV along a preassigned path, respecting assigned velocity, acceleration, and jerk constraints. The solution algorithm should be: 1) fast, since speed planning is made continuously throughout the workday, not only when an LGV receives a new task but also during the execution of the task itself, since conditions may change, e.g., if the LGV has to be halted for security reasons and 2) reliable, i.e., it should return solutions of high quality, because a better speed profile allows to save time and even small percentage improvements, say a 5% improvement, has a considerable impact on the productivity of the warehouse, and, thus, determines a significant economic gain. The algorithm that we propose meets these two requirements, and we believe that it can be a useful tool for LGV manufacturers and users. It is obvious that the proposed method also applies to the speed planning problem for vehicles other than LGVs, e.g., road vehicles. [ABSTRACT FROM AUTHOR]

We study a class of generic charging path optimization problems arising from emerging networking applications, where mobile chargers are dispatched to deliver energy to mobile agents (e.g., robots, drones, vehicles), which have specified tasks and mobility patterns. We instantiate our work by focusing on finding the charging path maximizing the number of nodes charged within a fixed time horizon. We show that this problem is APX-hard. By recursively decomposing the problem into sub-problems of searching sub-paths, we design quasi-polynomial-time algorithms achieving logarithmic approximation to the optimum charging path. Our approximation algorithms can be further adapted and extended to solve a variety of charging path optimization and scheduling problems with realistic constraints, such as limited time and energy budget. [ABSTRACT FROM AUTHOR]

This article is the second part of a two-part survey series on large-scale global optimization. The first part covered two major algorithmic approaches to large-scale optimization, namely, decomposition methods and hybridization methods, such as memetic algorithms and local search. In this part, we focus on sampling and variation operators, approximation and surrogate modeling, initialization methods, and parallelization. We also cover a range of problem areas in relation to large-scale global optimization, such as multiobjective optimization, constraint handling, overlapping components, the component imbalance issue and benchmarks, and applications. The article also includes a discussion on pitfalls and challenges of the current research and identifies several potential areas of future research. [ABSTRACT FROM AUTHOR]

This article focuses on developing a static output feedback (SOF) control scheme for Takagi–Sugeno fuzzy systems. The proposed SOF controller does not share the same premise membership functions with the model, which permits enhancing the flexibility in controller design and implementation. By contrast with the state feedback case, the SOF control generally results in nonconvex design conditions. To circumvent this problem, we develop a successive convex optimization algorithm, which is based on solving a sequence of more tractable convex optimization problems obtained by approximating the nonconvex constraints with some convex ones. As a heuristic algorithm, the validity of the developed successive convex optimization algorithm is highly affected by initial conditions, and, recognizing this, we put forward an iterative procedure for determining the feasible initial condition. Finally, two illustrative examples are presented to validate the efficiency of the proposed algorithms. [ABSTRACT FROM AUTHOR]

Rough clustering has attracted increasing attention due to well dealing with the fuzziness and uncertainty of data. It is well known that it needs to manually set the threshold to determine the upper and lower approximations of rough clusters, which may bring a great effect on the clustering performance. When applied to image segmentation, rough clustering is always sensitive to the initialized cluster centers and image noise. Furthermore, only one clustering criterion is considered in rough clustering, which cannot satisfy diverse practical requirements. To handle these issues, a particle competitive mechanism based multiobjective rough clustering algorithm (PCM-MORCA) for image segmentation is proposed. First, a rough intraclass compactness function considering the nonlocal spatial information derived from an image is constructed to overcome the sensitivity to image noise. Next, the constructed rough intraclass compactness function and an interclass separation function are optimized simultaneously to make cluster centers meet diverse segmentation requirements. Then, an adaptive threshold determination mechanism by which the threshold adaptively varies with the clustered data is presented to well determine the upper and lower approximations of rough clusters. After that, to effectively search appropriate cluster centers, a novel pair competition-based particle weight updating strategy is designed for multiobjective particle swarm optimization by improving the elite particle selection and particle update. Finally, a rough clustering index with the nonlocal spatial information is constructed for selecting the optimal solution for PCM-MORCA. Segmentation experiments on Berkeley and magnetic resonance images reveal that PCM-MORCA behaves well on the segmentation accuracy and noise robustness. [ABSTRACT FROM AUTHOR]

With an increasing penetration of distributed energy resources (DERs), it has become a public interest regarding how to efficiently manage large-scale DERs into wholesale markets. The existing literature has focused on various coordination methods including iteration-based (e.g., Lagrangian relaxation) and projection-based (e.g., vertex enumeration) ones, which may not work for the cases with complicated constraints due to curse of dimensionality. In this article, we propose an efficient projection-based method that adapts to characterizing the feasible region of active distribution networks with temporal-coupled constraints. The problem of finding the temporal-coupled feasible region is formulated as a max–min optimization program, aiming to determine the largest set allowing zero-valued slack variables. Based on Duality Principle, the max–min model is transformed into a solvable mixed-integer linear programming that can be efficiently optimized by off-the-shelf solvers. In contrast to the existing methods searching for a vertex from interior points, we develop an outer progressive approximation algorithm that generates feasibility cuts for each iteration. Case studies based on a modified IEEE 33-bus feeder and Caracas 141-bus system demonstrate the effectiveness and efficiency of our proposed method in characterizing the feasible region with large-scale temporal-coupled constraints. [ABSTRACT FROM AUTHOR]

This paper explores the non-convex composition optimization consisting of inner and outer finite-sum functions with a large number of component functions. This problem arises in important applications such as nonlinear embedding and reinforcement learning. Although existing approaches such as stochastic gradient descent (SGD) and stochastic variance reduced gradient (SVRG) descent can be applied to solve this problem, their query complexities tend to be high, especially when the number of inner component functions is large. Therefore, to significantly improve the query complexity of current approaches, we have devised the stochastic composition via variance reduction (SCVR). What's more, we analyze the query complexity under different numbers of inner function and outer function. Based on different kinds of estimation of inner component function, we also present the SCVRII algorithm, though the order of query complexities are the same with SCVR. Additionally, we propose an extension to handle the mini-batch cases, which improve the query complexity under the optimal mini-batch size. The experimental results validate our proposed algorithms and theoretical analyses. [ABSTRACT FROM AUTHOR]

The Traveling Salesman Problem (TSP) aims to find the shortest tour for a salesman who starts and ends in the same city and visits the remaining n − 1 cities exactly once. There are a number of common generalizations of the problem including the Multiple Traveling Salesman Problem (MTSP), where instead of one salesman, there are k salesmen and the same amount of individual tours are to be constructed. We consider the Euclidean version of the problem where the distances between the cities are calculated in two-dimensional Euclidean space. Both general the TSP and its Euclidean version are strongly NP-hard. Hence, approximation algorithms with a good practical behavior are of primary interest. We describe a general method for the solution of the Euclidean versions of the TSP (including MTSP) that yields approximation algorithms with a favorable practical behavior for large real-life instances. Our method creates special types of convex hulls, which serve as a basis for the constructions of our initial and intermediate partial solutions. Here, we overview three algorithms; one of them is for the bounded version of the MTSP. The proposed novel algorithm for the Euclidean TSP provides close-to-optimal solutions for some real-life instances. [ABSTRACT FROM AUTHOR]

Reorganizing bus frequencies to cater for the actual travel demands can significantly save the cost of the public transport system. Many, if not all, previous studies formulate this as a bus frequency optimization problem that tries to minimize passengers’ average waiting time. On the other hand, many investigations have confirmed that the user satisfaction drops faster as the waiting time increases. Consequently, this paper studies the bus frequency optimization problem considering the user satisfaction. Specifically, for the first time to our best knowledge, we study how to schedule the buses such that the total number of passengers who could receive their bus services within the waiting time threshold can be maximized. We propose two variants of the problem, FAST and FASTCO, to cater for different application needs and prove that both are NP-hard. To solve FAST effectively and efficiently, we first present an index-based $(1-1/e)$ (1 - 1 / e) -approximation algorithm. By exploiting the locality property of routes in a bus network, we further propose a partition-based greedy method that achieves a $(1-\rho)(1-1/e)$ (1 - ρ) (1 - 1 / e) approximation ratio. Then we propose a progressive partition-based greedy method to further boost the efficiency while achieving a $(1-\rho)(1-1/e-\varepsilon)$ (1 - ρ) (1 - 1 / e - ɛ) approximation ratio. For the FASTCO problem, two greedy-based heuristic methods are proposed. Experiments on a real city-wide bus dataset in Singapore have been conducted to verify the efficiency, effectiveness, and scalability of our methods in addressing FAST and FASTCO respectively. [ABSTRACT FROM AUTHOR]

Revenue maximization (RM) is one of the most important problems in social networks, which attempts to find a small subset of users that make the expected revenue maximized. It has been studied in depth before. However, most of the existing literature was based on nonadaptive seeding strategies and simple information diffusion models. It considered the number of influenced users as a measurement unit to quantify the revenue. Until the emergence of the collaborate game model, it considered the activity as a basic object to compute the revenue. An activity initiated by a user can only influence those users whose distances are within ${k}$ -hop from the initiator. Based on that, we adopt an adaptive seed strategy and formulate an RM under the size budget (RMSB) problem. If taking into account the product’s promotion, we extend it to an RM under the community budget problem, where the influence can be distributed over the whole network uniformly. We can prove that our objective function is adaptive monotone and not adaptive submodular, but it is adaptive submodular in some special cases. We study these two problems under both the special submodular cases and general nonsubmodular cases, and propose RMSBSolver and RMCBSolver to solve them with strong theoretical guarantees, respectively. In particular, we give a data-dependent approximation ratio by adaptive primal curvature for the RMSB in general nonsubmodular cases. Finally, we evaluate our proposed algorithms by conducting experiments on real datasets, and show the effectiveness and accuracy of our solutions. [ABSTRACT FROM AUTHOR]

We introduce a novel domination problem, which we call Dual Domination (DD). We assume that the nodes in a network are partitioned into two categories: Positive nodes (V +) and negative nodes (V −). We study the Maximum Bounded Dual Domination , where, given a bound k , the problem is to find a set D ⊆ V + , which maximizes the number of nodes dominated in V + , dominating at most k nodes in V −. We show that such problem is hard to approximate to a factor better than (1 − 1 / e). We give a polynomial time algorithm with approximation guaranteed (1 − e − 1 / Δ) , where Δ represents the maximum number of neighbors in V + of any node in V − , and an O (| V | k 2) time algorithm to solve the problem on trees. We also study two related problems named Maximum Dual Domination and minimum Negative Dual Domination. For both problems, we show hardness results and provide O (| V |) time algorithms on trees. [ABSTRACT FROM AUTHOR]

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

The design of a fuzzy neural network (FNN) has long been a challenging problem since most methods rely on approximation error to train an FNN, which may easily result in overfitting phenomenon to degrade the generalization performance. To improve the generalization performance, an FNN with a multiobjective optimization algorithm (MOO-FNN) is proposed in this article. First, the multilevel learning objectives are designed around the generalization performance to guide the training process of an FNN. Then, the method utilizes the approximation error, the structure complexity, and the output smoothness indicators instead of a single indicator to improve the evaluation accuracy of generalization performance. Second, an MOO algorithm with continuous–discrete variables is developed to optimize the FNN. Then, MOO is able to use a novel particle update method to adjust both the structure and parameters rather than adjusting them separately, thereby achieving suitable generalization performance of the FNN. Third, the convergence of MOO-FNN is analyzed in detail to guarantee its successful applications. Finally, the experimental studies of MOO-FNN have been performed on model identification of nonlinear systems to verify the effectiveness. The results illustrate that MOO-FNN has a significant improvement over some state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

Considering multi-user downlink ultra-high reliability and low latency communications (URLLC), this paper employs the artificial noise (AN) technique to establish a secure and covert broadcast communication paradigm for the first time. Specifically, a multi-antenna transmitter (Alice) broadcasts the confidential information to multiple legitimate users in the presence of a multi-antenna malicious warden (Willie) and a multi-antenna eavesdropper (Eve). It is well known that AN is an effective technique for securing the physical layer security (PLS) of signal transmissions. Nevertheless, AN emission also exposes the signal transmission and decreases the signal covertness. Taking into account the impact of short-packet URLLC transmissions, we investigate the joint optimization of the precoder and AN to maximize the secrecy rate under the covertness constraint. Although the considered problem is nonconvex, we propose a branch-reduce-and-bound (BRB)-based algorithm to solve it optimally. However, the nested-loop structure of the BRB-based algorithm incurs a high computational complexity. To strike a balance between the performance and computational complexity, we also propose a low-complexity penalty successive convex approximation (SCA)-based algorithm, whose performance approaches that of the optimal BRB-based algorithm, particularly in the low to medium transmit power regime. Simulation results demonstrate the excellent performance of our proposed optimization algorithms compared with various benchmark algorithms and unveil the importance of exploiting AN for secrecy provisioning. [ABSTRACT FROM AUTHOR]

With the integration of Mobile Edge Computing (MEC) and Network Function Virtualization (NFV), service providers are able to provide low-latency services to mobile users for profit. In this paper, we study the online service placement and request assignment problem in an MEC network, where service requests arrive one by one without the knowledge of future arrivals, and each arrived request demands a specific service with a tolerable service delay requirement with the aim to maximize the profit of the service provider, through admitting as many service requests as possible for a given monitoring period. This optimization objective is achieved by assigning service requests to appropriate cloudlets in the MEC network, pre-installing service instances into cloudlets to shorten service delays, and accommodating new services by revoking some idle service instances from cloudlets due to limited computing resources in MEC networks. In this paper, we first show that the problem is NP-hard. We then devise an efficient deep reinforcement learning algorithm for the online service placement and request assignment problem that consists of a deep reinforcement learning-based prediction mechanism for dynamic service placement, followed by a dynamic request assignment procedure to assign requests to cloudlets. We finally evaluate the performance of the proposed algorithms by conducting experiments through simulations. Simulation results demonstrate that the proposed algorithm is promising, improving performance by 46.8% compared with that of the comparison algorithms. [ABSTRACT FROM AUTHOR]

In this article, we consider the optimal coordination of automated vehicles at intersections under fixed crossing orders. We formulate the problem using direct optimal control and exploit the structure to construct a semidistributed primal-dual interior-point algorithm to solve it by parallelizing most of the computations. Differently from standard distributed optimization algorithms, where the optimization problem is split, in our approach we split the linear algebra steps, such that the algorithm takes the same steps as a fully centralized one, while still performing computations in a distributed fashion. We analyze the communication requirements of the algorithm, and propose an approximation scheme which can significantly reduce the data exchange. We demonstrate the effectiveness of the algorithm in hard but realistic scenarios, which show that the approximation leads to reductions in communicated data of almost 99% of the exact formulation, at the expense of less than 1% suboptimality. [ABSTRACT FROM AUTHOR]