Search

Transportation networks frequently employ hub-and-spoke network architectures to route flows between many origin and destination pairs. Hub facilities work as switching points for flows in large networks. In this study, we focus on a problem, called the single allocation hub-and-spoke network design problem. In the problem, the goal is to allocate each non-hub node to exactly one of the given hub nodes so as to minimize the total transportation cost. The problem is essentially equivalent to another combinatorial optimization problem, called the metric labeling problem. The metric labeling problem was first introduced by Kleinberg and Tardos in 2002, motivated by application to segmentation problems in computer vision and related areas. In this study, we deal with a case where the set of hubs forms a star, which is encountered especially in telecommunication networks. We propose a polynomial-time randomized approximation algorithm for the problem, whose approximation ratio is less than 5.281. Our algorithms solve a linear relaxation problem and apply dependent rounding procedures. [ABSTRACT FROM AUTHOR]

We call a (not necessarily properly) edge-colored graph edge-color-avoiding connected if after the removal of edges of any single color, the graph remains connected. For vertex-colored graphs, similar definitions of color-avoiding connectivity can be given. In this article, we investigate the problem of determining the maximum number of edges that can be removed from either an edge- or a vertex-colored, color-avoiding connected graph so that it remains color-avoiding connected. First, we prove that this problem is NP-hard, and then, we give a polynomial-time approximation algorithm for it. To analyze the approximation factor of this algorithm, we determine the minimum number of edges of color-avoiding connected graphs on a given number of vertices and with a given number of colors. Furthermore, we also consider a generalization of edge-color-avoiding connectivity to matroids. [ABSTRACT FROM AUTHOR]

Continual Learning (CL) plays a crucial role in enhancing learning performance for both new and previous tasks in continuous data streams, thus contributing to the advancement of cognitive computing. However, CL faces a fundamental challenge known as the stability-plasticity quandary. In this research, we present an innovative and effective CL algorithm called Primary Null Space Projection (PNSP) to strike a balance between network plasticity and stability. PNSP consists of three main components. Firstly, it leverages the NSP-LRA algorithm to project the gradient of network parameters from previous tasks into a meticulously designed null space. NSP-LRA harnesses high-dimensional geometric information extracted from the feature covariance matrix through low-rank approximation algorithm to obtain the basis of null space dynamically. This process constructs an innovation null space and ensures the continuous updating of orthonormal bases to accommodate changes in the input data. Secondly, we propose a Consistency-guided Task-specific Feature Learning (CTFL) mechanism to tackle the issue of catastrophic forgetting and facilitate continual learning. CTFL achieves this by aligning feature vectors and maintaining consistent feature learning directions, thereby preventing the loss of previously acquired knowledge. Lastly, we introduce Label Guided Self-Distillation (LGSD), a technique that utilizes true labels to guide the distillation process and incorporates a dynamic temperature mechanism to enhance performance. To evaluate the effectiveness of our proposed method, we conduct experiments on the CIFAR100 and TinyImageNet datasets. The results demonstrate significant improvements over state-of-the-art methods. We have made the implementation code of our approach available for reference. • Proposal of PNSP method: Addresses stability-plasticity dilemma in continual learning. • NSP-LRA: Dynamically constructs null space for minimizing interference. • CTFL mechanism: Ensures consistent feature learning directions. • LGSD technique: Incorporates true labels and dynamic temperature for enhanced distillation. [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]

We study the NP-complete Maximum Outerplanar Subgraph problem. The previous best known approximation ratio for this problem is 2 / 3. We propose a new approximation algorithm which improves the ratio to 7 / 10. [ABSTRACT FROM AUTHOR]

Much of the theory of estimation for exponential family models, which include exponential-family random graph models (ERGMs) as a special case, is well-established and maximum likelihood estimates (MLEs) in particular enjoy many desirable properties. However, in the case of many ERGMs, direct calculation of MLEs is impossible and therefore methods for approximating MLEs and/or alternative estimation methods must be employed. Many MLE approximation algorithms require an alternative estimate as a starting point. The maximum pseudo-likelihood estimator (MPLE) is frequently taken as this starting point. Here, we discuss a potentially large class of such alternatives based on the fact that, unlike the MLE, the MPLE fails to satisfy the so-called "likelihood principle". This means that different networks may have different MPLEs even if they have the same sufficient statistics. We exploit this fact here to search for improved starting values for approximation-based MLE methods. The method we propose has shown its merit in producing an MLE for a network dataset and model that had defied estimation using all other known methods. • Improving MCMC starting values. • Using simulated annealing for finding starting value. • Maximum pseudolikelihood and simulated annealing. • MLE, MPLE, and the likelihood principle. • Exponential family model for networks. [ABSTRACT FROM AUTHOR]

• A novel two-stage coordinated risk-averse distributionally robust optimization model for maintenance and generation schedules of wind turbines is proposed. • A risk-averse measurement method is combined with DRO model for considering the operation risks. • A feasible route generating algorithm for reducing the number of required binary variables is proposed. • The transformation of proposed model and the specific algorithm is proposed to solve the proposed model. • Test results show the computational accuracy and efficiency of the proposed method. The coordinated optimization of maintenance and generation schedules of multiple offshore wind farms (OWFs) bring great benefits in reducing the maintenance and operation cost of OWF cluster. Firstly, a two-stage coordinated risk-averse distributionally robust optimization (CRDRO) model for maintenance and generation schedules of wind turbines (WTs) in OWF cluster is proposed. This model takes into account uncertainties related to the prediction errors in WTs' maximum available active power outputs, the travel time of maintenance vessels, and the high operational cost risks associated with these uncertainties. A feasible route generating algorithm is designed to obtain all feasible maintenance combinations for WTs and the corresponding routes of maintenance vessels for the CRDRO model. The risk-averse term, which is a weighted sum of expected operation costs and GlueVaR value, is used to measure the tail risk of the worst probability distribution. To solve the two-stage CRDRO model, the risk-averse term is simplified into the form of expected value calculation, which can be further transformed into the tractable form by using the strong duality theorem. Finally, the two-stage CRDRO model is solved by the column-and-constraint generation algorithm, with the nonconvex sub-problem being addressed by the outer approximation algorithm. Case studies on an real-world cluster comprising three OWFs verify the correctness and efficiency of the proposed method, and demonstrate that the CRDRO model enhances the overall economic efficiency and reduces the high operational cost risk under extreme scenarios. [ABSTRACT FROM AUTHOR]

We consider the single-machine time-dependent scheduling problem with linearly deteriorating jobs arriving over time. Each job i is associated with a release time r i and a processing time p i (s i) = α i + β i s i , where α i , β i > 0 are parameters and s i is the job's start time. In this setting, the approximability of both single-machine minimum makespan and total completion time problems remains open. We develop new bounds and approximation results for the special case of the problems with uniform deterioration, i.e. β i = β , for each i. The main contribution is a O (1 + 1 / β) -approximation algorithm for the makespan problem and a O (1 + 1 / β 2) approximation algorithm for the total completion time problem. Further, we propose greedy constant-factor approximation algorithms for instances with β = O (1 / n) and β = Ω (n) , where n is the number of jobs. Our analysis is based on an approach for comparing computed and optimal schedules via bounding pseudomatchings. [ABSTRACT FROM AUTHOR]

K-best enumeration , which asks to output k -best solutions without duplication, is a helpful tool in data analysis for many fields. In such fields, graphs typically represent data. Thus subgraph enumeration has been paid much attention to such fields. However, k -best enumeration tends to be intractable since, in many cases, finding one optimum solution is NP-hard. To overcome this difficulty, we combine k -best enumeration with a concept of enumeration algorithms called approximation enumeration algorithms. As a main result, we propose a 4-approximation algorithm for minimal connected edge dominating sets which outputs k minimal solutions with cardinality at most 4 ⋅ OPT ‾ , where OPT ‾ is the cardinality of a minimum solution which is not outputted by the algorithm. Our proposed algorithm runs in O (n m 2 Δ) delay, where n , m , Δ are the number of vertices, the number of edges, and the maximum degree of an input graph. [ABSTRACT FROM AUTHOR]

Machine learning-based model predictive control (ML-MPC) has been developed to control nonlinear processes with unknown first-principles models. While ML models can capture nonlinear dynamics of complex systems, the complexity of ML models leads to increased computation time for real-time implementation of ML-MPC. To address this issue, in this work, we propose an explicit ML-MPC framework for nonlinear processes using multi-parametric programming. Specifically, a self-adaptive approximation algorithm is first developed to obtain a piecewise linear affine function that approximates the behaviors of ML models. Then, multi-parametric quadratic programming (mpQP) problems are formulated to generate the solution map for states in discretized state–space. Furthermore, to accelerate the implementation of explicit ML-MPC, a neighbor-first search algorithm is developed. Finally, an example of a chemical reactor is used to demonstrate the effectiveness of the explicit ML-MPC. • An explicit MPC framework for MPCs using a general class of ML models. • A self-adaptive algorithm for approximating ML models with the desired accuracy. • Neighbor-first search algorithm for accelerating implementation of explicit ML-MPC. • Improvement of computational efficiency demonstrated in a chemical process example. [ABSTRACT FROM AUTHOR]

In this paper, we propose a graph classification approach for automatically determining whether to use a monolithic or a decomposition-based solution method. In this approach, an optimization problem is represented as a graph that captures the structural and functional coupling among the variables and constraints of the problem via an appropriate set of features. Given this representation, a graph classifier can be built to assist a solver in selecting the best solution strategy for a given problem with respect to some metric of choice. The proposed approach is used to develop a classifier that determines whether a convex Mixed Integer Nonlinear Programming problem should be solved using branch and bound or the outer approximation algorithm. Finally, it is shown how the learned classifier can be incorporated into existing mixed integer optimization solvers. • A deep learning framework is proposed to decide when to use a decomposition. • A feature-based graph representation of optimization problems is proposed. • The proposed approach is applied to Mixed Integer Nonlinear optimization problems. • Integration of the proposed approach with optimization solvers is discussed. [ABSTRACT FROM AUTHOR]

Consensus of networked nonlinear nonparametric time-varying systems is studied, and the nonlinearity at input may possess arbitrary growth rate. In addition, the communication noise is also under consideration. The purely distributed control algorithm is designed on the basis of distributed stochastic approximation algorithm with expanding truncations (DSAAWET). The truncation mechanism neutralizes the divergent tendency caused by unknown nonlinearities and noises, which makes the algorithm well tackle more general nonlinearities with high growth rate and more complicated structure noises. We first prove the average consensus over fixed digraph, and then extend the results to averagely connected time-varying digraphs. Finally, the validity of the algorithm is justified by numerical simulations. [ABSTRACT FROM AUTHOR]

Damian and Pemmaraju (2002) [8] introduced leaf sector covers for circle graphs and presented an O (n 2) -time algorithm to find this data structure. They subsequently employed it as an algorithmic tool, leading to the development of an 8-approximation algorithm for the dominating set problem, a (2 + ε) -approximation scheme for the dominating set problem, and a (3 + ε) -approximation scheme for the total dominating set problem. In this paper, we have improved the time complexity from O (n 2) to O (n + m) for finding a leaf sector cover. Furthermore, we employed leaf sector covers as a powerful algorithmic tool to design a 10-approximation algorithm for the total dominating set problem and a 12-approximation algorithm for the paired-dominating set problem. Moreover, we also proposed a (2 + ε) -approximation scheme for the total dominating set problem and a (4 + ε) -approximation scheme for the paired-dominating set problem. The results presented above are currently the best algorithms for circle graphs. [ABSTRACT FROM AUTHOR]

Let T be a tessellation composed of equilateral triangular regions, where each region has an associated positive weight. We present two methods that discretize the space based on the placement of Steiner points in the cells of T. Using such a discretization, we can use Dijkstra's algorithm for computing the shortest path in the geometric graph obtained. This will lead us to two approximation algorithms for solving the Weighted Region Problem. For a given parameter ε ∈ (0 , 1 ] , the first discretization scheme provides an approximate path that is (1 + 0.428 ε) times better than the approximation given by Aleksandrov et al. (2005) [5]. The other discretization scheme uses at least ( ε + 2 ε + 4 ε + 4) log 2 ⁡ e fewer points per segment of the triangulation with the same approximation factor. [ABSTRACT FROM AUTHOR]

In crowdsourcing systems, a challenge arises in efficiently recruiting workers with unknown execution speed to complete tasks with precedence constraints within the shortest possible time. Recent research either only studies recruiting unknown workers or focuses on assigning tasks with precedence constraints, but few works consider both these factors. This paper aims to address this challenge considering all these factors by proposing a digital twin-assisted Combinatorial Multi-arm bandit based multi-round work Recruitment and task Scheduling (CMRS) scheme. Firstly, with the help of digital twin technology, we build digital twin models for crowdsourcing tasks and workers in digital twin layer of platform. And we formulate a Multi-round Workers recruitment and Task scheduling with Precedence constraints (MWTP) problem with the object of minimizing task completion time (makespan) to model the above challenging issue in crowdsourcing computing. The MWTP problem can be divided into two sub-problems, the task scheduling sub-problem and the worker recruitment sub-problem. Secondly, in the CMRS scheme, the differential evolution based task scheduling (DETS) algorithm and CUCB-based worker recruitment (CWR) method are proposed to solve them, respectively. Specifically, for the task scheduling sub-problem, we first propose a priority-driven based task scheduling (PDTS) approximation algorithm to produce a primary solution with an explicit approximation ratio. Then a DETS algorithm is proposed to use the solution of PDTS for initialization and generate a better solution that further improves the performance. For the unknown workers recruitment sub-problem, we use the Combinatorial Multi-Arm Bandit framework to model this, and propose CWR method to learn the computational capabilities of workers while maintaining good performance during multiple rounds of worker recruitment by adding a tuning term to balanced exploration and exploitation. Finally, verified by extensive comparison experiments, the CMRS scheme can achieve the best performance of makespan compared with the baselines in most cases. [ABSTRACT FROM AUTHOR]

The Cognitive Radio Network, incorporating Device-to-Device communication and a heterogeneous network, has garnered significant attention due to its ability to address spectrum shortage issues and optimize the efficient utilization of spectrum resources. However, resource allocation considering stochastic behavior has not been considered in existing studies. In this paper, our work aimed to maximize the throughput of the overall network considering multiple users under the umbrella of the Cognitive radio network assisted by amplify and forward relay. The constraints are treated as chance constraints with a probability of satisfaction in them, which leads to a non-convex mixed integer nonlinear problem which is an NP-Hard problem. To solve this problem an exhaustive search solution for optimal results is required. However, the computational burden always increases with the user equipment. Therefore, to obtain an optimal solution with having low computational burden, the Outer Approximation Algorithm is utilized in this research. To evaluate the desired results, extensive simulations have been carried out. The effectiveness of the proposed algorithm is verified by results in terms of throughput maximization under the impact of chance constraint formulation in the cognitive radio networks. [ABSTRACT FROM AUTHOR]

The fair k -center problem has been paid lots of attention recently. In the fair k -center problem, we are given a set X of points in a metric space and a parameter k ∈ Z + , where the points in X are divided into several groups, and each point is assigned a color to denote which group it is in. The goal is to partition X into k clusters such that the number of cluster centers with each color is equal to a given value, and the k -center problem objective is minimized. In this paper, we consider the fair k -center problem with outliers and capacity constraints, denoted as the fair k -center with outliers (F k CO) problem and the capacitated fair k -center (CF k C) problem, respectively. The outliers constraints allow up to z outliers to be discarded when computing the objective function, while the capacity constraints require that each cluster has size no more than L. In this paper, we design an Fixed-Parameter Tractability (FPT) approximation algorithm and a polynomial approximation algorithm for the above two problems. In particular, our algorithms give (1 + ϵ) -approximations with FPT time for the F k CO and CF k C problems in doubling metric space. Moreover, we also propose a 3-approximation algorithm in polynomial time for the F k CO problem with some reasonable assumptions. [ABSTRACT FROM AUTHOR]

We consider the product of determinantal point processes (DPPs), a point process whose probability mass is proportional to the product of principal minors of multiple matrices, as a natural, promising generalization of DPPs. We study the computational complexity of computing its normalizing constant , which is among the most essential probabilistic inference tasks. Our complexity-theoretic results (almost) rule out the existence of efficient algorithms for this task unless the input matrices are forced to have favorable structures. In particular, we prove the following: • Computing ∑ S det ⁡ (A S , S) p exactly for every (fixed) positive even integer p is UP -hard and Mod 3 P -hard, which gives a negative answer to an open question posed by Kulesza and Taskar [51]. • ∑ S det ⁡ (A S , S) det ⁡ (B S , S) det ⁡ (C S , S) is NP -hard to approximate within a factor of 2 O (| I | 1 − ε) or 2 O (n 1 / ε) for any ε > 0 , where | I | is the input size and n is the order of the input matrix. This result is stronger than the # P -hardness for the case of two matrices derived by Gillenwater [36]. • There exists a k O (k) n O (1) -time algorithm for computing ∑ S det ⁡ (A S , S) det ⁡ (B S , S) , where k is the maximum rank of A and B or the treewidth of the graph formed by nonzero entries of A and B. Such parameterized algorithms are said to be fixed-parameter tractable. These results can be extended to the fixed-size case. Further, we present two applications of fixed-parameter tractable algorithms given a matrix A of treewidth w : • We can compute a 2 n 2 p − 1 -approximation to ∑ S det ⁡ (A S , S) p for any fractional number p > 1 in w O (w p) n O (1) time. • We can find a 2 n -approximation to unconstrained maximum a posteriori inference in w O (w n) n O (1) time. [ABSTRACT FROM AUTHOR]

Deterministic time–frequency representations are commonly used in signal processing, particularly in audio processing. Whilst presenting many potential advantages, their probabilistic counterparts are not widely used, essentially because of the computational load and the lack of clear interpretability of the different underlying models. However, using state space models, they have been shown recently to be equivalent to Spectral Mixtures Gaussian processes (SM-GP). This pioneer work unlocks this problem and opens the path for the development of tractable and interpretable probabilistic time–frequency analysis. In this paper, we propose a relatively simple yet a significant improvement of that work in terms of computational complexity, flexibility and practical application. To do so, we use a recent approach for covariance approximation to develop an algorithm for faster inference of SM-GP, while opting for a frequency-domain approach to hyperparameter learning. We illustrate the practical potential of our method using voiced speech data. We first show that key speech features can be accurately learned from the data. Second, we show that our method can yield better performances in denoising. [ABSTRACT FROM AUTHOR]

Internet of Things (IoT) services deployed across different Cloud Service Providers (CSPs) require seamless migration across heterogeneous clouds. Sky Computing (SC) facilitates the requirement by implementing a coordinator with communication APIs among clouds. However, security concerns of CSPs prevent the coordinator from accessing detailed cloud hardware information, thereby hindering the assessment of Serving Ability (SA) and exacerbating delays in service delivery. To ensure delay experience, we designed a loss-aware coordinator SkyCap for the multi-CSP collaboration in SC. First, to assess the SA of clouds with available information, we design a loss-aware SA assessment mechanism AdaSA that collects delay experience and Packet Loss Ratio (PLR) information for SA assessment. Since the uncontrollable PLR can increase service delay, we incorporate PLR as a disturbing factor in SA assessment to ensure a more precise evaluation. Second, to maximize the admission profit of the collaboration, we design two approximation algorithms within SkyCap to serve requests. Since the coordinator may deploy services in batches, we design a delay-aware offline algorithm AdaOff to serve requests simultaneously, while ensuring the computing capacity of clouds and the delay requirement of requests. Meanwhile, for asynchronously arriving requests, we design an ability-aware online algorithm AdaOn to serve requests in real-time, while guaranteeing the computing capacity of clouds, SA of clouds, and delay requirement of requests. Finally, extensive theoretical analysis and experimental validation confirm the performance of the coordinator SkyCap. The SA assessment mechanism AdaSA outperforms existing solutions in SA assessment by ensuring at most 1% deviation, especially in high-PLR scenarios. Meanwhile, the algorithm AdaOff exhibits a remarkable 20% improvement over the state-of-the-art in admission profit while ensuring stringent service delay. Concurrently, the algorithm AdaOn surpasses existing solutions, achieving a nearly 10% enhancement in both admission profit and service delay. In summary, the coordinator SkyCap stands out in theoretical groundwork and practical implementation, offering advancements in the SA assessment, admission profit, and service delay. [ABSTRACT FROM AUTHOR]

The coordination among drones and ground vehicles for last-mile delivery has gained significant interest in recent years. In this paper, we study multiple drone delivery scheduling problem (MDSP) [1] for last-mile delivery, where we have a set of drones with an identical battery budget and a set of delivery locations; along with profit for delivery, cost, and delivery time intervals. The objective of the MDSP is to find conflict-free schedules for each drone such that the total profit gained is maximum subject to the battery constraint of the drones. This paper proposes an optimal pseudo-polynomial algorithm and a fully polynomial time approximation scheme (FPTAS) for the single drone delivery scheduling problem (SDSP). Also, we propose two approximation algorithms of factor 1 3 for the MDSP with some constraints on the number of drones. We formulate the problem for the heterogeneous case, where the drones have non-identical battery capacities, and propose a 1 6 ρ -approximation algorithm, where ρ is the ratio between the minimum and maximum battery capacity of the drones. • An optimal pseudo-polynomial algorithm and FPTAS for the single drone delivery scheduling problem is proposed. • Two approximation algorithms for the multiple drone delivery scheduling problem are proposed. • An approximation algorithm for the multiple heterogeneous drone delivery scheduling problem is proposed. • We analyzed the approximation factors of all the aforementioned proposed algorithms and time complexities. [ABSTRACT FROM AUTHOR]

• A novel nonconvex nonlocal low-rank tensor approximation reconstruction algorithm with hyper-Laplacian priori (HL-NRTA) is proposed for high fidelity CASSI reconstruction. The algorithm can simultaneously incorporate the global spectral correlation, spatial nonlocal self-similarity and hyper-Laplacian priori of HSI, and thus effectively combines local and non-local similarity information from fused spectral and spatial perspectives. • An efficient optimization algorithm is designed based on the Alternating Direction Method of Multipliers (ADMM) framework with the GST algorithm and Fast Fourier Transform (FFT) being adopted to accelerate the solution of the proposed model. • Extensive reconstruction results on the public HSI datasets and the real data of our CASSI system demonstrate the superiority of the proposed HL-NLTA model compared to several state-of-the-art CASSI reconstruction methods in terms of quantitative metrics and visual effects. Low-quality reconstruction is one main factor that greatly limits the development of snapshot compressive imaging (SCI) systems. The common algorithms usually unfold a 3D hyperspectral image (HSI) into a vector or matrix which inevitably corrupts the intrinsic structure of the HSI and insufficiently discovers its prior information. To fully exploit the underlying structures and internal correlations of the HSIs, this paper proposes a novel non-convex model based on Non-Local low-rank Tensor Approximation with Hyper-Laplacian priori (HL), named HL-NLTA, which effectively combines local and non-local similarity information from fused spectral and spatial perspectives. Specifically, a non-local low-rank tensor model based on the minimax concave plus (MCP) penalty and log sum (LS) penalty separately is developed which can simultaneously exploit two intrinsic properties of HSI, i.e., global correlation along the spectral domain (GCAS) and non-local self-similarity along the spatial domain (NSAS). Furthermore, the Hyper-Laplacian priori regularized through a non-convex ℓ p (0 < p < 1) norm can preserve well the spectral and spatial structure. An optimization algorithm based on the alternating direction multiplier method (ADMM) framework is designed and accelerated by the Generalized shrinkage/thresholding (GST) algorithm and the fast Fourier transform (FFT) to solve the new nonconvex model. Extensive simulation results on public datasets and experimental results on our real CASSI system indicate that the proposed method enables high-fidelity HSI reconstructions in terms of simultaneous spatial structure detail recovery and spectral preservation. These results verify the effectiveness of the proposed model for snapshot compressive imaging (e.g., Coded aperture snapshot spectral imaging CASSI). [ABSTRACT FROM AUTHOR]

The maximization of non-negative monotone submodular functions under a certain constraint is intensively studied. However, there are few works considering the maximization of non-monotone non-submodular functions, which even might be negative. These functions also have many applications, such as optimal marketing for revenue maximization over social networks, budget allocation problems, and Epidemic transmission, etc. In our paper, we discuss the maximization of the non-monotone non-submodular functions under a knapsack constraint, which even might be negative, and explore the performance under the greedy algorithm. We obtain some improved approximate ratios, for the functions with different properties, such as the non-negative weak-monotone weak-submodular functions, and the weak-submodular weak-supermodular functions that might be negative. Moreover, we generalize the results to the functions with weak subadditivity and curvature. [ABSTRACT FROM AUTHOR]

We study a constrained version of the Geometric Hitting Set problem where we are given a set of points, partitioned into pairwise disjoint subsets, and a set of intervals. The objective is to hit all the intervals with a minimum number of points such that if we select a point from a subset, we must select all the points from that subset. We consider two special cases of the problem where each subset can have at most 2 and 3 points. If each subset contains at most 2 points and the intervals are disjoint, we show that the problem admits a polynomial-time algorithm. On the contrary, if each subset contains at most t points, where t ≥ 2 , and the intervals are overlapping, we show that the problem becomes NP - Hard. Further, when each subset contains at most t points where t ≥ 3 , and the intervals are disjoint, we prove that the problem is NP - Hard , and we provide two constant factor approximation algorithms for this problem. We also study the problem from the parameterized complexity perspective. If the intervals are disjoint, then we prove that the problem is in FPT when parameterized by the size of the solution. We also complement this result by giving a lower bound in the size of the kernel for disjoint intervals, and we also provide a polynomial kernel when the size of all subsets is bounded by a constant. [ABSTRACT FROM AUTHOR]

We investigate the error of the randomized Milstein algorithm for solving scalar jump–diffusion stochastic differential equations. We provide a complete error analysis under substantially weaker assumptions than those known in the literature. In case the jump-commutativity condition is satisfied, we prove optimality of the randomized Milstein algorithm by establishing matching lower bounds. Moreover, we give some insight into the multidimensional case by investigating the optimal convergence rate for the approximation of jump–diffusion type Lévys' areas. Finally, we report numerical experiments that support our theoretical findings. [ABSTRACT FROM AUTHOR]

The anti-Ramsey number a r (G , H) with input graph G and pattern graph H , is the maximum positive integer k such that there exists an edge coloring of G using k colors, in which there are no rainbow subgraphs isomorphic to H in G. (H is rainbow if all its edges get distinct colors). The concept of anti-Ramsey number was introduced by Erdős et al. in 1973. Thereafter, several researchers investigated this concept in the combinatorial setting. Recently, Feng et al. revisited the anti-Ramsey problem for the pattern graph K 1 , t (for t ≥ 3) purely from an algorithmic point of view. For a graph G and an integer q ≥ 2 , an edge q -coloring of G is an assignment of colors to edges of G , such that the edges incident on a vertex span at most q distinct colors. The maximum edge q-coloring problem seeks to maximize the number of colors in an edge q -coloring of the graph G. Note that the optimum value of the edge q -coloring problem of G equals a r (G , K 1 , q + 1). Here, we study a r (G , K 1 , t) , the anti-Ramsey number of stars, for each fixed integer t ≥ 3 , both from combinatorial and algorithmic point of view. The first of our main results presents an upper bound for a r (G , K 1 , q + 1) , in terms of number of vertices and the minimum degree of G. The second one improves this result for the case of triangle-free input graphs. Our third main result presents an upper bound for a r (G , K 1 , q + 1) in terms of | E (G ≤ (q − 1)) | , which is a frequently used lower bound for a r (G , K 1 , q + 1) and maximum edge q -coloring in the literature. All our results have algorithmic consequences. [ABSTRACT FROM AUTHOR]

• Propose a novel data-driven, model-free framework. • Development of a hybrid knowledge-guided improved simultaneous perturbation stochastic approximation algorithm. • Validation of the effectiveness and efficiency of the proposed method in a systematic way. Steam generator level control systems play a crucial role in ensuring safe, economical, and stable operation of nuclear power plants. However, traditional control systems exhibit limited efficiency in commissioning and are susceptible to human error. Additionally, traditional parameter tuning methods are typically experienced-based, cumbersome, and time-consuming, making it challenging to obtain optimal parameters. To address these issues, we propose a hybrid knowledge-guided improved simultaneous perturbation stochastic approximation algorithm (HK-SPSA) to optimize the control parameters of steam generator level control systems. Firstly, the algorithm utilizes iteration point adjacency information to approximate the current optimization process status and guide the adaptive adjustment of the iteration step size. Secondly, it utilizes composite gradient information generated by the estimated historical and current gradients to guide the optimization direction and the tuning of iteration step size. Simulation experiments have shown that HK-SPSA improves optimization performance and reduces the costs of optimization and adjustment compared to traditional methods. [ABSTRACT FROM AUTHOR]

We initiate the study of a generalization of the class cover problem [Cannon and Cowen [1] , Bereg et al. [2] ] the generalized class cover problem , where we are allowed to misclassify some points provided we pay an associated positive penalty for every misclassified point. Two versions: single coverage and multiple coverage , of the generalized class cover problem are investigated. We study five different variants of both versions of the generalized class cover problem with axis-parallel strips and axis-parallel half-strips extending to different directions in the plane, thus extending similar work by Bereg et al. (2012) [2] on the class cover problem. We prove that the multiple coverage version of the generalize class cover problem with axis-parallel strips are in P , whereas the single coverage version is NP -hard. A factor 2 approximation algorithm is provided for the later problem. The APX -hardness result is also shown for the single coverage version. For half-strips extending to exactly one direction, both the single and multiple coverage versions can be solved in polynomial time using dynamic programming. In the case of half-strips extending to two orthogonal directions, we prove the class cover problem is NP -hard followed by APX -hard. This gives improve hardness results compare to Bereg et al. (2012) [2] , where they proved the class cover problem with half-strips oriented in four different directions is NP -hard. These NP - and APX -hardness results can directly apply to both single and multiple versions. Finally, constant factor approximation algorithms are provided for half-strips extending to more than one direction. [ABSTRACT FROM AUTHOR]

Discrete random variables are essential ingredients in various artificial intelligence problems. These include the estimation of the probability of missing the deadline in a series-parallel schedule and the assignment of suppliers to tasks in a project in a manner that maximizes the probability of meeting the overall project deadline. The solving of such problems involves repetitive operations, such as summation, over random variables. However, these computations are NP-hard. Therefore, we explore techniques and methods for approximating random variables with a given support size and minimal Kolmogorov distance. We examine both the general problem of approximating a random variable and a one-sided version in which over-approximation is allowed but not under-approximation. We propose several algorithms and evaluate their performance through computational complexity analysis and empirical evaluation. All the presented algorithms are optimal in the sense that given an input random variable and a requested support size, they return a new approximated random variable with the requested support size and minimal Kolmogorov distance from the input random variable. Our approximation algorithms offer useful estimations of probabilities in situations where exact computations are not feasible due to NP-hardness complexity. [ABSTRACT FROM AUTHOR]

Surrogate-assisted evolutionary algorithms (SAEAs) are a promising approach for solving expensive multiobjective optimization problems, but they often cannot address high-dimensional problems. Although one common approach to overcoming this challenge is to construct reliable surrogates, their accuracy inevitably deteriorates in a high-dimensional search space. Thus, this paper presents a novel SAEA based on scalarization function approximation, which is designed to strengthen its robustness against this deterioration. The proposed algorithm constructs an approximation model for each scalarization function defined in a decomposition-based framework. Each decomposed problem is then solved using multiple independent models trained for its neighbor problems. The intent is to decrease the risk of search performance degradations caused by unreliable approximations and retain the redundancy of the surrogate-assisted search to hedge the risk of over-fitting. Furthermore, each approximation model is adapted to a promising region of its corresponding decomposed problem to reduce the complexity of model fitting given a limited number of training samples. Experimental results show that the proposed algorithm is competitive with state-of-the-art SAEAs adapted for high-dimensional problems. [ABSTRACT FROM AUTHOR]

The influence maximization problem asks to find a small number of early adopters of a product in a social network, such that the expected number of total adoptions is maximized over the network. The problem has been well-studied, but most of the studies focus on the case of a single product or purely competitive products. This paper proposes a new influence diffusion model for multiple complementary products, namely, the comparative linear threshold (Com-LT) model. Under the Com-LT model, we model the complementary relation by reducing the thresholds of nodes. With this model, we study two problems: SelfInfMax and CompInfMax. We prove that these two problems are both NP-Hard under the Com-LT model. For both the SelfInfMax and the CompInfMax problem, we theoretically analyze the monotonicity and submodularity, and accordingly leverage lower bound optimization to devise non-trivial effective approximation algorithms. We conduct experiments over 4 real-world datasets. The experimental results demonstrate the correctness and efficiency of the proposed algorithms. • We study the complementary version of the influence maximization problem. • We propose Com-LT model to describe the influence spread of non- competitive products. • We studied the SelfInfMax and the CompInfMax problem and show their hardness. • We propose approximation algorithms with high quality feasible solutions. • We conduct experiments on real networks and show the effectiveness of our algorithms. [ABSTRACT FROM AUTHOR]

We consider a natural problem dealing with weighted packet selection across a rechargeable link, which e.g., finds applications in cryptocurrency networks. The capacity of a link (u , v) is determined by how many nodes u and v allocate for this link. Specifically, the input is a finite ordered sequence of packets that arrive in both directions along a link. Given (u , v) and a packet of weight x going from u to v , node u can either accept or reject the packet. If u accepts the packet, the capacity on link (u , v) decreases by x. Correspondingly, v 's capacity on (u , v) increases by x. If a node rejects the packet, this will entail a cost affinely linear in the weight of the packet. A link is "rechargeable" in the sense that the total capacity of the link has to remain constant, but the allocation of capacity at the ends of the link can depend arbitrarily on the nodes' decisions. The goal is to minimise the sum of the capacity injected into the link and the cost of rejecting packets. We show that the problem is NP-hard, but can be approximated efficiently with a ratio of (1 + ε) ⋅ (1 + 3) for some arbitrary ε > 0. [ABSTRACT FROM AUTHOR]

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

We consider 2-connectivity network design problems in which we are given a graph and seek a min-size 2-connected subgraph that satisfies a prescribed property. • In the 1 -Connectivity Augmentation problem the goal is to augment a connected graph by a minimum size edge subset of a specified edge set such that the augmented graph is 2-connected. We breach the natural approximation ratio 2 for this problem, and also for the more general Crossing Family Cover problem. • In the 2 -Connected Dominating Set problem, we seek a minimum size 2-connected subgraph that dominates all nodes. We give the first non-trivial approximation algorithm with expected approximation ratio O (σ (n) ⋅ log 3 ⁡ n) , where σ (n) = O (log ⁡ n ⋅ log ⁡ log ⁡ n ⋅ (log ⁡ log ⁡ log ⁡ n) 3). The unifying technique of both results is a reduction to the Subset Steiner Connected Dominating Set problem. Such a reduction was known for edge-connectivity, and we extend it to 2-node connectivity problems. We show that the same method can be used to obtain easily polylogarithmic approximation ratios that are not too far from the best known ones for several other problems. [ABSTRACT FROM AUTHOR]

This work considers to achieve near-optimal operation for a class of batch processes by employing self-optimizing control (SOC). Comparing with a continuous one, a batch process exhibits stronger nonlinearity with dynamics because of the non-steady operation condition. This necessitates a global version of SOC to achieve satisfactory performance. Meanwhile, it also makes the existing global SOC (gSOC) not directly applicable to batch processes due to the causality amongst variables. Therefore, it is necessary to extend the original gSOC to batch processes. In addition to the nonconvexity challenge of the original gSOC problem, the new extension for batch processes has to face even more challenges. Particularly, the causality due to dynamics of batch processes brings in structural constraints on controlled variables (CVs), making a CV selection problem even more difficult. To address these challenges, the gSOC problem is recast in a vectorized formulation and it is proved that the structural constraints considered are linear in the vectorized formulation. Moreover, a novel shortcut method is proposed to efficiently find sub-optimal but more transparent solutions for this problem. The effectiveness of the new approach is validated through a case study of a fed-batch reactor, where CVs are constructed through a combination matrix with a repetitive structure, resulting in a simple SOC scheme. This simplicity facilitates the implementation of the SOC approach and enhances its practical applicability and robustness. • Extends global SOC (gSOC) methodology to batch processes for the first time. • Proves certain structural constraints on CV combination matrix are linear. • Develops new convex approximation algorithm to solve gSOC with constraints. [ABSTRACT FROM AUTHOR]

This paper investigates two flow shop scheduling problems with two machines A and B , and a single transporter V. In the first problem, the transporter V is located at machine A initially, each job has to be processed first on A , then transported to B for further processing. While in the second problem, the transporter V is located at machine B initially, each job needs to be processed first on A , then on B , finally transported to the destination. In both problems, the transporter V can carry up to c (where c is a constant and c ≥ 1) jobs at a time and the objective is to minimize the makespan. For the former problem, the best approximation algorithm guarantees a worst-case ratio bound of (5 3 + ε) , while for the latter one, the best approximation algorithm provides a worst-case ratio bound of 2. For each problem, we design a polynomial-time approximation scheme (PTAS). [ABSTRACT FROM AUTHOR]

The fair k -median problem is one of the important clustering problems. The current best approximation ratio is 4.675 for this problem with 1-fairness violation, which was proposed by Bercea et al. [APPROX-RANDOM'2019]. To our best knowledge, there is no available approximation algorithm for this problem without any fairness violation in doubling metrics. In this paper, we consider the fair k -median problem in doubling metrics and general metrics. We provide the first QPTAS for the fair k -median problem based on the hierarchical decomposition and dynamic programming process in doubling metrics. For applying a dynamic programming process to solve this problem, the distances from portals to facilities cannot be directly enumerated since each client may not be assigned to its closest open facility. To overcome the difficulties caused by the fairness constraints, we construct an auxiliary graph and use minimum weighted perfect matching to get the cost between the portals of each block and the ones in its children. In order to satisfy the fairness constraints, we bound the fairness constraints of each open facility in the leaves of the split-tree based on the relation between the subproblem and the subproblems of its children. To obtain the assignment of the given instance and remove the fairness violation, we construct a new b -value min-cost max-flow model based on the set of open facilities. For the fair k -median problem in general metrics, we present a polynomial-time approximation algorithm with ratio O (log ⁡ k). Our approximation algorithm for the fair k -median problem in doubling metrics is the first result for the corresponding problem without any fairness violation in doubling metrics. [ABSTRACT FROM AUTHOR]

A k -submodular function takes k distinct, non-overlapping subsets of a ground set as input and outputs a value. It is a generalization of the well-known submodular function, which is the case when k = 1 and takes a single subset as input. We study the problem of maximizing a non-negative k -submodular function under a knapsack constraint. Greedy+Singleton is an algorithm that chooses the better solution between the fully greedy solution and the best single-element solution, with query complexity and running time of O (n 2 k). We show that Greedy+Singleton has an approximation ratio of 0.273 for monotone functions, which improves the previous analysis of 0.158 in the literature. Moreover, we give the first analysis of Greedy+Singleton for non-monotone k -submodular functions, and prove an approximation ratio of 0.219. [ABSTRACT FROM AUTHOR]

The priority model was introduced to capture "greedy-like" algorithms. Motivated by the success of advice complexity in the area of online algorithms, the fixed priority model was extended to include advice, and a reduction-based framework was developed for proving lower bounds on the amount of advice required to achieve certain approximation ratios in this rather powerful model. To capture most of the algorithms that are considered greedy-like, the even stronger model of adaptive priority algorithms is needed. We extend the adaptive priority model to include advice. We modify the reduction-based framework from the fixed priority case to work with the more powerful adaptive priority algorithms, simplifying the proof of correctness and strengthening all previous lower bounds by a factor of two in the process. As evidence that adding advice to adaptive priority algorithms extends both adaptive priority algorithms and online algorithms with advice, we present a purely combinatorial adaptive priority algorithm with advice for Minimum Vertex Cover on triangle-free graphs of maximum degree three. Our algorithm achieves optimality and uses at most 7 n / 22 bits of advice. No adaptive priority algorithm without advice can achieve optimality without advice, and we prove that an online algorithm with advice needs more than 7 n / 22 bits of advice to reach optimality. We show connections between exact algorithms and priority algorithms with advice. The branching in branch-and-reduce algorithms can be seen as trying all possible advice strings, and all priority algorithms with advice that achieve optimality define corresponding exact algorithms, priority exact algorithms. Lower bounds on advice-based adaptive algorithms imply lower bounds on running times of exact algorithms designed in this way. [ABSTRACT FROM AUTHOR]

Submodular maximization is one of the central topics in combinatorial optimization. It has found numerous applications in the real world. In the past decades, a series of algorithms have been proposed for this problem. However, most of the state-of-the-art algorithms are randomized. There remain non-negligible gaps with respect to approximation ratios between deterministic and randomized algorithms in submodular maximization. In this paper, we propose deterministic algorithms with improved approximation ratios for non-monotone submodular maximization. Specifically, for the matroid constraint, we provide a deterministic 0.283 − o (1) approximation algorithm, while the previous best deterministic algorithm only achieves a 1/4 approximation ratio. For the knapsack constraint, we provide a deterministic 1/4 approximation algorithm, while the previous best deterministic algorithm only achieves a 1/6 approximation ratio. For the linear packing constraints with large widths, we provide a deterministic 1 / 6 − ϵ approximation algorithm. To the best of our knowledge, there is currently no deterministic approximation algorithm for the constraints. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the diversity-aware fair k -supplier problem, which involves selecting k facilities from a set F that consists of m disjoint groups, subject to a constraint on the maximum number of facilities selected from each group. The goal is to ensure fairness in the selection process and avoids any demographic group from over-representation. While the classical k -supplier problem is known to be NP-hard to solve and is even NP-hard to approximate within a factor of less than 3, we present an efficient 5-approximation algorithm for the diversity-aware k -supplier problem based on maximum matching. [ABSTRACT FROM AUTHOR]

• Incremental variational formulation is developed for chemomechanical problem of heterogeneous composites. • Computation Homogenization-based FE2 solving algorithm is realized for heterogeneous composite. • Chemomechanical properties of composites are solved by two-scale consistent tangential solving algorithm. • The 'moment of mass concentration' is discussed for heterogeneous composites under mass diffusion. The chemomechanical properties of heterogeneous composites under mass diffusion are of significance in modern advanced technology and engineering applications. A homogenization-based two-scale chemomechanical model is developed for heterogeneous composites undergoing chemical mass diffusion. A two-scale incremental variational formulation is established for heterogeneous composites consisting of multiconstituents featuring local dissimilar diffusion-deformation properties. The minimization problems for coupled chemomechanical behaviors are solved for both macrostructure and microstructure contexts, where the macroscopic material properties are extracted from the results of local boundary value problem on the nested representative volume elements (RVEs). Through a staggered finite element method (FEM) implementation procedure, the proposed homogenization-based two-scale solution algorithm is implemented in the FEM package ABAQUS (V6.14). The developed variational model and tangential algorithm is checked by solving chemomechanical properties of particles enforced composite, where several numerical examples are conducted applying two-scale solution algorithm and validated by full-scale simulations. Parametric studies are carried out on the size effects of RVEs, with respect to the 'inertia effect' associated with 'moment of mass concentration', and the coupling mechanisms are discussed for mechanical and chemical solutions. To the end, the inelastic dissipations are solved on subscale BVPs and their effects on the mechanical deformation and chemical mass diffusion are checked. The contributions of this work are mainly two-folds. One is the theoretical advance for self-consistent homogenization modeling of the coupled multi-physics of heterogeneous composites, and a rigorous FE2 solution procedure. The other is providing numerical reference for evaluation of approximation algorithm as well as advanced data-driven method, which is needed for high-efficient material design. [ABSTRACT FROM AUTHOR]

Nash equilibrium is one of the most influential solution concepts in game theory. With the development of computer science and artificial intelligence, there is an increasing demand on Nash equilibrium computation, especially for Internet economics and multi-agent learning. This paper reviews various algorithms computing the Nash equilibrium and its approximation solutions in finite normal-form games from both theoretical and empirical perspectives. For the theoretical part, we classify algorithms in the literature and present basic ideas on algorithm design and analysis. For the empirical part, we present a comprehensive comparison on the algorithms in the literature over different kinds of games. Based on these results, we provide practical suggestions on implementations and uses of these algorithms. Finally, we present a series of open problems from both theoretical and practical considerations. • A classification on Nash equilibrium algorithms in the literature with basic ideas on design and analysis presented. • A comprehensive comparison on Nash equilibrium algorithms in the literature over different kinds of games. • Practical suggestions on implementations and uses of Nash equilibrium algorithms. [ABSTRACT FROM AUTHOR]

For a graph G = (V , E) without an isolated edge, a set D ⊆ E is an edge total dominating set of G if every edge e ∈ E is adjacent to at least one edge of D. The Minimum Edge Total Dominating Set problem is to compute a minimum cardinality edge total dominating set of G. It is known that the decision version of the problem is NP-complete for bipartite graphs, chordal graphs, and planar graphs. On the positive side, the problem is efficiently solvable for trees. In this paper, we further study the complexity of this problem in other graph classes. We design a linear-time algorithm to compute a minimum cardinality edge total dominating set in chain graphs, a subclass of bipartite graphs. We also propose linear-time algorithms for two subclasses of chordal graphs, namely, split graphs and proper interval graphs with no cut vertices. In addition, we show that the problem is APX-complete for graphs with maximum degree 3 and propose an approximation algorithm for the problem in k -regular graphs, where k ≥ 4. We discuss the complexity difference between the Minimum Edge Dominating Set problem and Minimum Edge Total Dominating Set problem which seem to be closely related. [ABSTRACT FROM AUTHOR]