Search

• This is the first research of calibrateing quantile regression forests with conformal predictive systems for better performance. • Out-of-bag predictions of quantile regression forests are employed to make full use of data and improve computational efficiency. • With analysis of quantile regression forests, our proposed weighed approach performs best in the comparison experiments. Quantile regression forests (QRF) is a generalization of random forests for quantile regression, which can also output probabilistic prediction for regression problems. QRF delivers a nonlinear and nonparametric way of probabilistic prediction and is widely used in many applications. To improve the prediction quality of QRF, this paper builds conformal predictive systems (CPSs) on top of QRF to calibrate the probabilistic prediction, which is the first attempt of combining CPSs with QRF to our best knowledge. Conformal predictive systems aim to produce valid probabilistic predictions in machine learning community, whose predictive distributions are compatible with realizations. Three algorithms are proposed in this paper. One is a fast approximation algorithm to split conformal predictive system. Building on that, the other two algorithms are proposed based on the out-of-bag samples and the weighted approach of QRF. Experiments with 20 public data sets were conducted and the results demonstrated that our algorithms are empirically valid and compared favourably with the original QRF. [ABSTRACT FROM AUTHOR]

This paper studies the problem of programming a robotic panda gardener to keep a bamboo garden from obstructing the view of the lake by your house. The garden consists of n bamboo stalks with known daily growth rates and the gardener can cut at most one bamboo per day. As a computer scientist, you found out that this problem has already been formalized in [Gąsieniec et al., SOFSEM'17] as the Bamboo Garden Trimming (BGT) problem , where the goal is that of computing a perpetual schedule (i.e., the sequence of bamboos to cut) for the robotic gardener to follow in order to minimize the makespan , i.e., the maximum height ever reached by a bamboo. Two natural strategies are Reduce-Max and Reduce-Fastest(x). Reduce-Max trims the tallest bamboo of the day, while Reduce-Fastest(x) trims the fastest growing bamboo among the ones that are taller than x. It is known that Reduce-Max and Reduce-Fastest(x) achieve a makespan of O (log ⁡ n) and 4 for the best choice of x = 2 , respectively. We prove the first constant upper bound of 9 for Reduce-Max and improve the one for Reduce-Fastest(x) to 3 + 5 2 < 2.62 for x = 1 + 1 5 . Another critical aspect stems from the fact that your robotic gardener has a limited amount of processing power and memory. It is then important for the algorithm to be able to quickly determine the next bamboo to cut while requiring at most linear space. We formalize this aspect as the problem of designing a Trimming Oracle data structure, and we provide three efficient Trimming Oracles implementing different perpetual schedules, including those produced by Reduce-Max and Reduce-Fastest(x). • We prove the first constant upper bound on the makespan attained by Reduce-Max by showing that it is at most 9. • We improve the best known upper bound on the makespan of Reduce-Fastest(x) to 3 + 5 2 < 2.62 (for x = 1 + 1 5 ). • We show that Reduce-Fastest(2) (the former best choice for x), achieves a makespan of 19 6 (improved from 4). • We design compact data structures (Trimming Oracles) that are able to quickly report the next bamboo to cut. • Our Trimming Oracles implement Reduce-Max, Reduce-Fastest(x), and a novel trimming strategy achieving a makespan of 2. [ABSTRACT FROM AUTHOR]

We give two approximation algorithms solving the Stochastic Boolean Function Evaluation (SBFE) problem for symmetric Boolean functions. The first is an O (log n) -approximation algorithm, based on the submodular goal-value approach of Deshpande, Hellerstein and Kletenik. Our second algorithm, which is simple, is based on the algorithm solving the SBFE problem for k -of- n functions, due to Salloum, Breuer, and Ben-Dov. It achieves a (B − 1) approximation factor, where B is the number of blocks of 0's and 1's in the standard vector representation of the symmetric Boolean function. As part of the design of the first algorithm, we prove that the goal value of any symmetric Boolean function is less than n (n + 1) / 2. Finally, we give an example showing that for symmetric Boolean functions, minimum expected verification cost and minimum expected evaluation cost are not necessarily equal. This contrasts with a previous result, given by Das, Jafarpour, Orlitsky, Pan and Suresh, which showed that equality holds in the unit-cost case. [ABSTRACT FROM AUTHOR]

We consider the multistage framework introduced in (Gupta et al., Eisenstat et al., both in ICALP 2014), where we are given a time horizon and a sequence of instances of a (static) combinatorial optimization problem (one for each time step), and the goal is to find a sequence of solutions (one for each time step) reaching a tradeoff between the quality of the solutions in each time step and the stability/similarity of the solutions in consecutive time steps. We first introduce a novel rounding scheme, tailored for multistage problems, that accounts for the moving cost (or stability revenue) of adjacent solutions. Using this rounding scheme, we propose improved approximation algorithms for the multistage variants of Prize-Collecting Steiner Tree and Prize-Collecting Traveling Salesman problems. Furthermore, we introduce a 2-approximation algorithm for multistage Multi-Cut on trees, and we also show that our general scheme can be extended to maximization problems, by providing a 0.75-approximation algorithm for the multistage variant of MaxSat. [ABSTRACT FROM AUTHOR]

We consider stochastic algorithms derived from methods for solving deterministic optimization problems, especially comparison-based algorithms derived from stochastic approximation algorithms with a constant step-size. We develop a methodology for proving geometric convergence of the parameter sequence { θ n } n ⩾ 0 of such algorithms. We employ the ordinary differential equation (ODE) method, which relates a stochastic algorithm to its mean ODE, along with a Lyapunov-like function Ψ such that the geometric convergence of Ψ (θ n) implies – in the case of an optimization algorithm – the geometric convergence of the expected distance between the optimum and the search point generated by the algorithm. We provide two sufficient conditions for Ψ (θ n) to decrease at a geometric rate: Ψ should decrease "exponentially" along the solution to the mean ODE, and the deviation between the stochastic algorithm and the ODE solution (measured by Ψ) should be bounded by Ψ (θ n) times a constant. We also provide practical conditions under which the two sufficient conditions may be verified easily without knowing the solution of the mean ODE. Our results are any-time bounds on Ψ (θ n) , so we can deduce not only the asymptotic upper bound on the convergence rate, but also the first hitting time of the algorithm. The main results are applied to a comparison-based stochastic algorithm with a constant step-size for optimization on continuous domains. [ABSTRACT FROM AUTHOR]

• The possibility of depth cameras for volume measurement of agricultural products was examined. • A novel fast and accurate volume measuring method for Pleurotus eryngii was proposed based on single view. • Circular disk approximation algorithm and linear regression algorithm based on single factor (project area, length and width) were used for comparison with the proposed method. • The proposed method achieved a MAE=6.61 % on 198 Pleurotus eryngii samples. The volume of Pleurotus eryngii plays an important role in postharvest packaging industry. The traditional manual detection method is labor-intensive and cannot meet the production requirements. In this study, a depth camera-based computer vision system was developed to collect data, and a novel method was proposed to accurately measure the volume of Pleurotus eryngii. In the first step, the RGB and depth images of Pleurotus eryngii were divided into cap and stipe parts according to the concave regions. The volume of the cap was calculated using the Monte Carlo method. As for the stipe, an improved circular disk approximation algorithm was applied, dividing each slice into smaller square pieces to obtain a more precise result. Furthermore, the measured volume was optimized by calculating the volumes of gaps of neck and root which are not visible from the top view. Compared with the manual measuring method, the experimental results demonstrate that our method achieved a Mean Absolute Error of 6.61 %, a Root Mean Squared Error of 12.890 cm3, and a R-squared value of 0.966. Moreover, the average processing time of a sample was only 0.412 s, while manual measurements took about 2 min. All of these results indicated that the proposed method is effective, convenient, time-saving, non-destructive and highly precisise. Therefore, it can be successfully adapted for measuring the volume of Pleurotus eryngii in practical application. [ABSTRACT FROM AUTHOR]

The support of a flow x in a network is the subdigraph induced by the arcs uv for which x (u v) > 0. We discuss a number of results on flows in networks where we put certain restrictions on structure of the support of the flow. Many of these problems are NP-hard because they generalize linkage problems for digraphs. For example deciding whether a network N = (D , s , t , c) has a maximum flow x such that the maximum out-degree of the support D x of x is at most 2 is NP-complete as it contains the 2-linkage problem as a very special case. Another problem which is NP-complete for the same reason is that of computing the maximum flow we can send from s to t along p paths (called a maximum p -path-flow) in N. Baier et al. (2005) gave a polynomial time algorithm which finds a p -path-flow x whose value is at least 2 3 of the value of a optimum p -path-flow when p ∈ { 2 , 3 } , and at least 1 2 when p ≥ 4. When p = 2 , they show that this is best possible unless P=NP. We show for each p ≥ 2 that the value of a maximum p -path-flow cannot be approximated by any ratio larger than 9 11 , unless P=NP. We also consider a variant of the problem where the p paths must be disjoint. For this problem, we give an algorithm which gets within a factor 1 H (p) of the optimum solution, where H (p) is the p 'th harmonic number (H (p) ∼ ln ⁡ (p)). We show that in the case where the network is acyclic, we can find such a maximum p -path-flow in polynomial time for every p. We determine the complexity of a number of related problems concerning the structure of flows. For the special case of acyclic digraphs, some of the results we obtain are in some sense best possible. [ABSTRACT FROM AUTHOR]

Given an edge-weighted metric complete graph with n vertices, the maximum weight metric triangle packing problem is to find a set of n / 3 vertex-disjoint triangles with the total weight of all triangles in the packing maximized. Several simple methods can lead to a 2/3-approximation ratio. However, this barrier is not easy to break. Chen et al. proposed a randomized approximation algorithm with an expected ratio of (0.66768 − ε) for any constant ε > 0. In this paper, we improve the approximation ratio to (0.66835 − ε). Furthermore, we can derandomize our algorithm. [ABSTRACT FROM AUTHOR]

In a delegation problem, a principal P with commitment power tries to pick one out of n options. Each option is drawn independently from a known distribution. Instead of inspecting the options herself, P delegates the information acquisition to a rational and self-interested agent A. After inspection, A proposes one of the options, and P can accept or reject. Delegation is a classic setting in economic information design with many prominent applications, but the computational problems are only poorly understood. In this paper, we study a natural online variant of delegation, in which the agent searches through the options in an online fashion. For each option, he has to irrevocably decide if he wants to propose the current option or discard it, before seeing information on the next option(s). How can we design algorithms for P that approximate the utility of her best option in hindsight? We show that in general P can obtain a Θ (1 / n) -approximation and extend this result to ratios of Θ (k / n) in case (1) A has a lookahead of k rounds, or (2) A can propose up to k different options. We provide fine-grained bounds independent of n based on three parameters. If the ratio of maximum and minimum utility for A is bounded by a factor α , we obtain an Ω (log ⁡ log ⁡ α / log ⁡ α) -approximation algorithm, and we show that this is best possible. Additionally, if P cannot distinguish options with the same value for herself, we show that ratios polynomial in 1 / α cannot be avoided. If there are at most β different utility values for A , we show a Θ (1 / β) -approximation. If the utilities of P and A for each option are related by a factor γ , we obtain an Ω (1 / log ⁡ γ) -approximation, where O (log ⁡ log ⁡ γ / log ⁡ γ) is best possible. [ABSTRACT FROM AUTHOR]

• Proposing an iterative approach to optimize the grid topology and redispatch. • Redispatch and topology optimization are decoupled to reduce complexity. • Linearized models are used to meet the computation time requirements. • The results show that useful topological actions can be selected. • The approach shows promising computation times for use in congestion management. The selection of Remedial Actions (RA) to ensure system security is a highly complex task performed by Transmission System Operators (TSOs). Phase shifting transformer (PST) tap changes and active power changes of generation units (redispatch) are some RA available in Security Constrained Optimal Power Flow (SCOPF) simulations within the operational planning processes. Topological RA are not part of these SCOPF yet, as the optimization thereof adds high complexity to the existing optimization problem. To overcome this complexity, this paper introduces an iterative approach that decouples topology optimization from redispatch & PST optimization. Linearized models of RA are used to meet computation time requirements. Exemplary investigations of the presented method were performed based on modified IEEE 39-Bus, 118-Bus and PEGASE-1354-Bus grid models. Within the scope of these investigations, the method shows good results and a great potential for the reduction of congestions and required redispatch through topological RA. In order to eliminate inaccuracies of the approach and to further improve its suitability for use in grid operation, a need for future investigations and possible further developments were identified. [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]

k -Clustering partitions a set of n points in a metric space into at most k clusters in a way that makes the resulted clusters satisfy both the homogeneity and the separation criteria. The diameter of a cluster is the maximum distance between pairs of points in the cluster, and the split of a cluster is the minimum distance between points of the cluster and ones outside the cluster. In this paper, we propose a new criterion for measuring the goodness of clusters: The ratio of the minimum cluster split to the maximum cluster diameter (abbr. RSD). We study the following two optimization problems: Maximizing RSD without and with cardinality constraints, i.e., each cluster should consist of at least N points. For both problems with k ≥ 3 , it is NP-hard to achieve a factor of (1 2 + ϵ) approximation for any ϵ > 0. For k = 2 , we solve the two problems optimally; For k ≥ 3 , we present a 1 2 -approximation and a 1 4 -approximation algorithm for the two problems, respectively. [ABSTRACT FROM AUTHOR]

• Definition and study of the extension variants of the connected vertex cover problem (Ext-CVC), and of the Non-Separating Independent Set problem (Ext-NSIS). • Solvability and hardness results for Ext-CVC , notably in bipartite graphs of maximum degree 3 and in weakly triangulated graphs, applying also to Ext-NSIS. • Formulation of the concept of Price of Extension (PoE) as the approximation ratio for the problem Max Ext-CVC (resp., Min Ext-NSIS). • Lower bounds for PoE of Max Ext-CVC in general and bipartite graphs; proof that it is equal to 1 in chordal graphs, carrying over to Min Ext-NSIS. We consider extension variants of Vertex Cover and Independent Set , following a line of research initiated in [10]. In particular, we study the Ext-CVC and the Ext-NSIS problems: given a graph G = (V , E) and a vertex set U ⊆ V , does there exist a minimal connected vertex cover (respectively, a maximal non-separating independent set) S , such that U ⊆ S (respectively, U ⊇ S). We present hardness results for both problems, for certain graph classes such as bipartite, chordal and weakly chordal. To this end we exploit the relation of Ext-CVC to Ext-VC , that is, to the extension variant of Vertex Cover. We also study the Price of Extension (PoE) , a measure that reflects the distance of a vertex set U to its maximum efficiently computable subset that is extensible to a minimal connected vertex cover, and provide negative and positive results for PoE in general and special graphs. [ABSTRACT FROM AUTHOR]

• We study a k-wise generalization of the Kemeny rule. • We study the properties of this distance, and of the induced aggregation rule. • We introduce a k-wise counterpart of the majority graph. • We provide computational complexity results for the aggregation problem. • A polytime 2-approximation algorithm is provided for the aggregation problem. In this paper, we advocate the use of setwise contests for aggregating a set of input rankings into an output ranking. We propose a generalization of the Kemeny rule where one minimizes the number of k -wise disagreements instead of pairwise disagreements (one counts 1 disagreement each time the top choice in a subset of alternatives of cardinality at most k differs between an input ranking and the output ranking). After an algorithmic study of this k -wise Kemeny aggregation problem, we introduce a k -wise counterpart of the majority graph. This graph reveals useful to divide the aggregation problem into several sub-problems, which enables to speed up the exact computation of a consensus ranking. By introducing a k -wise counterpart of the Spearman distance, we also provide a 2-approximation algorithm for the k -wise Kemeny aggregation problem. We conclude with numerical tests. [ABSTRACT FROM AUTHOR]

We study the Student-Project Allocation problem with lecturer preferences over Projects (spa-p). In this context it is known that stable matchings can have different sizes and the problem of finding a maximum size stable matching is NP-hard. There are two known approximation algorithms for max-spa-p , with performance guarantees 2 and 3 2. We show that max-spa-p is polynomial-time solvable if there is only one lecturer involved, and NP-hard to approximate within some constant c > 1 if there are two lecturers involved. We also show that this problem remains NP-hard if each preference list is of length at most 3, with an arbitrary number of lecturers. We then describe an Integer Programming (IP) model to enable max-spa-p to be solved optimally in the general case. Following this, we present results arising from an empirical evaluation that investigates how the solutions produced by the approximation algorithms compare to optimal solutions obtained from the IP model, with respect to the size of the stable matchings constructed, on instances that are both randomly-generated and derived from real datasets. [ABSTRACT FROM AUTHOR]

We consider the maximum vertex-weighted matching problem (MVM) for non-bipartite graphs in which non-negative weights are assigned to the vertices of a graph and a matching that maximizes the sum of the weights of the matched vertices is desired. In earlier work we have described a 2 / 3 -approximation algorithm for the MVM on bipartite graphs (Florin Dobrian et al., 2019). Here we show that a 2 / 3 -approximation algorithm for MVM on non-bipartite graphs can be obtained by restricting the length of augmenting paths to at most three. The algorithm has time complexity O (m log Δ + n log n) , where n is the number of vertices, m is the number of edges, and Δ is the maximum degree of a vertex. The approximation ratio of the algorithm is obtained by considering failed vertices , i.e., vertices that the approximation algorithm fails to match but the exact algorithm does. We show that there are two distinct heavier matched vertices that we can charge each failed vertex to. Our proof techniques characterize the structure of augmenting paths in a novel way. We have implemented the 2 / 3 -approximation algorithm and show that it runs in under a minute on graphs with tens of millions of vertices and hundreds of millions of edges. We compare its performance with five other algorithms: an exact algorithm for MVM, an exact algorithm for the maximum edge-weighted matching (MEM) problem, as well as three approximation algorithms. The approximation algorithms include a 1 / 2 -approximation algorithm for MVM, and (2 / 3 − ε) - and (1 − ε) -approximation algorithms for the MEM. In our test set of nineteen problems, there are graphs on which the exact algorithms fail to terminate in 100 hours. In addition, the new 2 / 3 -approximation algorithm for MVM outperforms the other approximation algorithms by either being faster (often by orders of magnitude) or obtaining better weights. [ABSTRACT FROM AUTHOR]

We present a (1 + k k + 2) -approximation algorithm for the Maximum k - dependent Set problem on bipartite graphs for any k ≥ 1. For a graph with n vertices and m edges, the algorithm runs in O (k m n) time and improves upon the previously best-known approximation ratio of 1 + k k + 1 established by Kumar et al. (2014). Our proof also indicates that the algorithm retains its approximation ratio when applied to the (more general) class of König–Egerváry graphs. [ABSTRACT FROM AUTHOR]

• There are knight's tours in n × n boards with less than 9.25 n turns and 12 n crossings. • Any knight's tour in an n × n board has over 5.99 n turns and 4 n crossings. • Using a 2 × 2 formation of parallel knight moves helps reduce both turns and crossings. • A new knight's tour algorithm minimizes turns and crossings simultaneously. • Our new knight's tour algorithm can be generalized to 3D boards and similar pieces. We introduce two new metrics of "simplicity" for knight's tours: the number of turns and the number of crossings. We give a novel algorithm that produces tours with 9.25 n + O (1) turns and 12 n + O (1) crossings on an n × n board, and we show lower bounds of (6 − ϵ) n and 4 n − O (1) on the respective problems of minimizing these metrics. Hence, our algorithm achieves approximation ratios of 9.25 / 6 + o (1) and 3 + o (1). Our algorithm takes linear time and is fully parallelizable, i.e., the tour can be computed in O (n 2 / p) time using p processors in the CREW PRAM model. We generalize our techniques to rectangular boards, high-dimensional boards, symmetric tours, odd boards with a missing corner, and tours for (1 , 4) -leapers. In doing so, we show that these extensions also admit a constant approximation ratio on the minimum number of turns, and on the number of crossings in most cases. [ABSTRACT FROM AUTHOR]

Future cities promise to be more autonomous than ever, largely owing to our ability of coordinating complex systems in real time: fleets of self-driving cars will offer on-demand transportation services, delivery drones will fly parcels in our skies, power plants will provide renewable energy reliably. In many of these systems, there is no single decision-maker with full information and authority. Instead, the system performance greatly depends on the decisions made by interacting entities with local information and limited communication capabilities. Game theory, intended as the study of multi-agent decision-making, is a fitting paradigm to tackle many of the associated challenges. Moving from this observation, in this paper we review how tools and ideas from game theory can be brought to bear on the coordination of multi-agent systems. At the heart of the proposed approach is the design and influence of agents' preferences so that their local optimization induces a desirable system behavior. Its applicability spans a variety of settings irrespective of whether the decision makers are strategic (e.g., drivers in a road network), or not (e.g., delivery drones). Along the way, we also discuss future research directions and connections with related research areas including algorithmic game theory, incentive and mechanism design, economics, computational complexity, and approximation algorithms. [ABSTRACT FROM AUTHOR]

We study the efficacy and efficiency of deep generative networks for approximating probability distributions. We prove that neural networks can transform a low-dimensional source distribution to a distribution that is arbitrarily close to a high-dimensional target distribution, when the closeness is measured by Wasserstein distances and maximum mean discrepancy. Upper bounds of the approximation error are obtained in terms of the width and depth of neural network. Furthermore, it is shown that the approximation error in Wasserstein distance grows at most linearly on the ambient dimension and that the approximation order only depends on the intrinsic dimension of the target distribution. On the contrary, when f -divergences are used as metrics of distributions, the approximation property is different. We show that in order to approximate the target distribution in f -divergences, the dimension of the source distribution cannot be smaller than the intrinsic dimension of the target distribution. [ABSTRACT FROM AUTHOR]

Dense subgraph discovery is an important graph-mining primitive with a variety of real-world applications. One of the most well-studied optimization problems for dense subgraph discovery is the densest subgraph problem, where given an edge-weighted undirected graph G = (V , E , w) , we are asked to find S ⊆ V that maximizes the density d (S) , i.e., half the weighted average degree of the induced subgraph G [ S ]. This problem can be solved exactly in polynomial time and well-approximately in almost linear time. However, a densest subgraph has a structural drawback, namely, the subgraph may not be robust to vertex/edge failure. Indeed, a densest subgraph may not be well-connected, which implies that the subgraph may be disconnected by removing only a few vertices/edges within it. In this paper, we provide an algorithmic framework to find a dense subgraph that is well-connected in terms of vertex/edge connectivity. Specifically, we introduce the following problems: given a graph G = (V , E , w) and a positive integer/real k , we are asked to find S ⊆ V that maximizes the density d (S) under the constraint that G [ S ] is k -vertex/edge-connected. For both problems, we propose polynomial-time (bicriteria and ordinary) approximation algorithms, using classic Mader's theorem in graph theory and its extensions. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a graph on n vertices, where d (v) denotes the degree of vertex v , and t (v) is a threshold associated with v. We consider a process in which initially a set S of vertices becomes active, and thereafter, in discrete time steps, every vertex v that has at least t (v) active neighbors becomes active as well. The set S is contagious if eventually all V becomes active. The target set selection problem TSS asks for the smallest contagious set. TSS is NP-hard and moreover, notoriously difficult to approximate. In the conservative special case of TSS, t (v) > 1 2 d (v) for every v ∈ V. In this special case, TSS can be approximated within a ratio of O (Δ) , where Δ = max v ∈ V [ d (v) ]. In this work we introduce a more general class of TSS instances that we refer to as conservative on average (CoA), that satisfy the condition ∑ v ∈ V t (v) > 1 2 ∑ v ∈ V d (v). We design approximation algorithms for some subclasses of CoA. For example, if t (v) ≥ 1 2 d (v) for every v ∈ V , we can find in polynomial time a contagious set of size O ̃ Δ ⋅ O P T 2 , where O P T is the size of a smallest contagious set in G. We also provide several hardness of approximation results. For example, assuming the unique games conjecture, we prove that TSS on CoA instances with Δ ≤ 3 cannot be approximated within any constant factor. We also present results concerning the fixed parameter tractability of CoA TSS instances. [ABSTRACT FROM AUTHOR]

In this paper, we consider the following variations of the Line Segment Disk Cover (LSDC) problem. LSDC-H : In this version of LSDC problem, we are given a set S = { s 1 , s 2 , ... , s n } of n horizontal line segments of arbitrary length and an integer k (≥ 1). Our aim is to cover all segments in S with k disks of minimum radius centered at arbitrary points in the plane. LSDC-A : In this version of LSDC problem, we are given a set S = { s 1 , s 2 , ... , s n } of n line segments of arbitrary length with arbitrary orientation and an integer k (≥ 1). Our aim is to cover all segments in S with k disks of minimum radius centered at arbitrary points in the plane. LSDC-D : In the discrete version of LSDC problem, we are given a set S = { s 1 , s 2 , ... , s n } of n line segments of arbitrary length with arbitrary orientation and a set D = { d 1 , d 2 , ... , d m } of m disks of unit radius. Our aim is to cover all segments in S with the minimum number of disks in D i.e., find D ′ such that S ⊂ ⋃ d ∈ D ′ d , where D ′ ⊆ D is of minimum cardinality. For LSDC-H and LSDC-A problems, we propose (1 + ε) -factor approximation algorithms, which run in O ( (max { 4 δ − 2 , 1 }) k n (| log r o p t | + log ⌈ 1 ρ ⌉)) time and O ( (max { 4 δ − 2 , 1 }) k n log n (| log r o p t | + log ⌈ 1 ρ ⌉)) time, respectively, where r o p t is the minimum radius of k disks which cover all segments in S , and δ > 0 , ρ > 0 and ε > 0 are fixed constants such that ε ≥ (δ + δ ρ + ρ). For LSDC-D problem, we propose a (1 + ε) -factor approximation algorithm (PTAS), which runs in O (m 2 (8 2 ε) 2 + 3 + m 2 n) time, where 0 < ε ≤ 2 , and a (9 + ε) -factor approximation algorithm, which runs in O (m (5 + 18 ε) log m + m 2 n) time, where 0 < ε ≤ 6. For LSDC-D problem, we also have developed a faster approximation algorithm based on a simple greedy strategy. The running time and the approximation factor of the greedy algorithm are O (k (m n + m log m)) and δ 1 δ k , respectively, where k is the output size, and δ 1 and δ k are the largest sums of lengths of parts of line segments that lie within a disk in the first and the last (k t h) iteration of the greedy algorithm, respectively. [ABSTRACT FROM AUTHOR]

We present a low-constant approximation for the metric k -median problem on insertion-only streams using O (ε − 3 k log n) space. In particular, we present a streaming (O (ε − 3 k log n) , 2 + ε) -bicriterion solution that reports cluster weights. Running the offline approximation algorithm due to Byrka et al. (2015) on this bicriterion solution yields a (17. 66 + ε) -approximation (Guha et al., 2003; Charikar et al., 2003; Braverman et al., 2011). Our result matches the best-known space requirements for streaming k -median clustering while significantly improving the approximation accuracy. We also provide a lower bound, showing that any polylog (n) -space streaming algorithm that maintains an (α , β) -bicriterion must have β ≥ 2. Our technique breaks the stream into segments defined by jumps in the optimal clustering cost, which increases monotonically as the stream progresses. By storing an accurate summary of recent segments of the stream and a lower-space summary of older segments, our algorithm maintains a (O (ε − 3 k log n) , 2 + ε) -bicriterion solution for the entirety of the stream. In addition to our main result, we introduce a novel construction that we call a candidate set. This is a collection of points that, with high probability, contains k points that yield a near-optimal k -median cost. We present an algorithm called monotone faraway sampling (MFS) for constructing a candidate set in a single pass over a data stream. We show that using this candidate set in tandem with a coreset speeds up the search for a solution set of k cluster centers upon termination of the data stream. While coresets of smaller asymptotic size are known, comparative simplicity of MFS makes it appealing as a practical technique. [ABSTRACT FROM AUTHOR]

A data-based value iteration algorithm with the bidirectional approximation feature is developed for discounted optimal control. The unknown nonlinear system dynamics is first identified by establishing a model neural network. To improve the identification precision, biases are introduced to the model network. The model network with biases is trained by the gradient descent algorithm, where the weights and biases across all layers are updated. The uniform ultimate boundedness stability with a proper learning rate is analyzed, by using the Lyapunov approach. Moreover, an integrated value iteration with the discounted cost is developed to fully guarantee the approximation accuracy of the optimal value function. Then, the effectiveness of the proposed algorithm is demonstrated by carrying out two simulation examples with physical backgrounds. [ABSTRACT FROM AUTHOR]