Search

We establish a list of characterizations of bounded twin-width for hereditary classes of totally ordered graphs: as classes of at most exponential growth studied in enumerative combinatorics, as monadically NIP classes studied in model theory, as classes that do not transduce the class of all graphs studied in finite model theory, and as classes for which model checking first-order logic is fixed-parameter tractable studied in algorithmic graph theory. This has several consequences. First, it allows us to show that every hereditary class of ordered graphs either has at most exponential growth, or has at least factorial growth. This settles a question first asked by Balogh et al. [5] on the growth of hereditary classes of ordered graphs, generalizing the Stanley-Wilf conjecture/Marcus-Tardos theorem. Second, it gives a fixed-parameter approximation algorithm for twin-width on ordered graphs. Third, it yields a full classification of fixed-parameter tractable first-order model checking on hereditary classes of ordered binary structures. Fourth, it provides a model-theoretic characterization of classes with bounded twin-width. Finally, it settles the small conjecture [8] in the case of ordered graphs. [ABSTRACT FROM AUTHOR]

A constraint satisfaction problem (CSP), \(\textsf {Max-CSP}(\mathcal {F})\) , is specified by a finite set of constraints \(\mathcal {F}\subseteq \lbrace [q]^k \rightarrow \lbrace 0,1\rbrace \rbrace\) for positive integers q and k. An instance of the problem on n variables is given by m applications of constraints from \(\mathcal {F}\) to subsequences of the n variables, and the goal is to find an assignment to the variables that satisfies the maximum number of constraints. In the (γ ,β)-approximation version of the problem for parameters 0 ≤ β ≤ γ ≤ 1, the goal is to distinguish instances where at least γ fraction of the constraints can be satisfied from instances where at most β fraction of the constraints can be satisfied. In this work, we consider the approximability of this problem in the context of sketching algorithms and give a dichotomy result. Specifically, for every family \(\mathcal {F}\) and every β < γ, we show that either a linear sketching algorithm solves the problem in polylogarithmic space or the problem is not solvable by any sketching algorithm in \(o(\sqrt {n})\) space. In particular, we give non-trivial approximation algorithms using polylogarithmic space for infinitely many constraint satisfaction problems. We also extend previously known lower bounds for general streaming algorithms to a wide variety of problems, and in particular the case of q=k=2, where we get a dichotomy, and the case when the satisfying assignments of the constraints of \(\mathcal {F}\) support a distribution on \([q]^k\) with uniform marginals. Prior to this work, other than sporadic examples, the only systematic classes of CSPs that were analyzed considered the setting of Boolean variables q = 2, binary constraints k =2, and singleton families \(|\mathcal {F}|=1\) and only considered the setting where constraints are placed on literals rather than variables. Our positive results show wide applicability of bias-based algorithms used previously by [47] and [41], which we extend to include richer norm estimation algorithms, by giving a systematic way to discover biases. Our negative results combine the Fourier analytic methods of [56], which we extend to a wider class of CSPs, with a rich collection of reductions among communication complexity problems that lie at the heart of the negative results. In particular, previous works used Fourier analysis over the Boolean cube to initiate their results and the results seemed particularly tailored to functions on Boolean literals (i.e., with negations). Our techniques surprisingly allow us to get to general q-ary CSPs without negations by appealing to the same Fourier analytic starting point over Boolean hypercubes. [ABSTRACT FROM AUTHOR]

We consider the numerical taxonomy problem of fitting a positive distance function \({\mathcal {D}:{S\choose 2}\rightarrow \mathbb {R}_{\gt 0}}\) by a tree metric. We want a tree T with positive edge weights and including S among the vertices so that their distances in T match those in \(\mathcal {D}\). A nice application is in evolutionary biology where the tree T aims to approximate thebranching process leading to the observed distances in \(\mathcal {D}\) [Cavalli-Sforza and Edwards 1967]. We consider the total error, that is, the sum of distance errors over all pairs of points. We present a deterministic polynomial time algorithm minimizing the total error within a constant factor. We can do this both for general trees and for the special case of ultrametrics with a root having the same distance to all vertices in S. The problems are APX-hard, so a constant factor is the best we can hope for in polynomial time. The best previous approximation factor was O((log n)(log log n)) by Ailon and Charikar [2005], who wrote "determining whether an O(1) approximation can be obtained is a fascinating question." [ABSTRACT FROM AUTHOR]

We identify a sufficient condition, treewidth-pliability, that gives a polynomial-time algorithm for an arbitrarily good approximation of the optimal value in a large class of Max-2-CSPs parameterised by the class of allowed constraint graphs (with arbitrary constraints on an unbounded alphabet). Our result applies more generally to the maximum homomorphism problem between two rational-valued structures. The condition unifies the two main approaches for designing a polynomial-time approximation scheme. One is Baker's layering technique, which applies to sparse graphs such as planar or excluded-minor graphs. The other is based on Szemerédi's regularity lemma and applies to dense graphs. We extend the applicability of both techniques to new classes of Max-CSPs. However, we prove that the condition cannot be used to find solutions (as opposed to approximating the optimal value) in general. Treewidth-pliability turns out to be a robust notion that can be defined in several equivalent ways, including characterisations via size, treedepth, or the Hadwiger number. We show connections to the notions of fractional-treewidth-fragility from structural graph theory, hyperfiniteness from the area of property testing, and regularity partitions from the theory of dense graph limits. These may be of independent interest. In particular, we show that a monotone class of graphs is hyperfinite if and only if it is fractionally-treewidth-fragile and has bounded degree. [ABSTRACT FROM AUTHOR]

The article focuses on studying randomized greedy matching algorithms, particularly the Modified Randomized Greedy (MRG) algorithm and its weaker version named Random Decision Order (RDO). It mentions the RDO algorithm is shown to provide a 0.639-approximation for bipartite graphs and a 0.531-approximation for general graphs, leading to a substantial improvement in the approximation ratio of MRG.

The study of approximate matching in the Massively Parallel Computations (MPC) model has recently seen a burst of breakthroughs. Despite this progress, we still have a limited understanding of maximal matching which is one of the central problems of parallel and distributed computing. All known MPC algorithms for maximalmatching either take polylogarithmic time which is considered inefficient, or require a strictly superlinear space of n1+Ω(1) per machine. In this work, we close this gap by providing a novel analysis of an extremely simple algorithm, which is a variant of an algorithm conjectured to work by Czumaj, Lacki, Madry, Mitrovic, Onak, and Sankowski [15]. The algorithm edge-samples the graph, randomly partitions the vertices, and finds a random greedy maximal matching within each partition.We show that this algorithm drastically reduces the vertex degrees. This, among other results, leads to an O(log log Δ) round algorithm for maximal matching with O(n) space (or even mildly sublinear in n using standard techniques). As an immediate corollary, we get a 2 approximate minimum vertex cover in essentially the same rounds and space, which is the optimal approximation factor under standard assumptions. We also get an improved O(log log Δ) round algorithm for 1 + ε approximate matching. All these results can also be implemented in the congested clique model in the same number of rounds. [ABSTRACT FROM AUTHOR]

Estimating ranks, quantiles, and distributions over streaming data is a central task in data analysis and monitoring. Given a stream of n items from a data universe equipped with a total order, the task is to compute a sketch (data structure) of size polylogarithmic in n. Given the sketch and a query item y, one should be able to approximate its rank in the stream, i.e., the number of stream elements smaller than or equal to y. Most works to date focused on additive εn error approximation, culminating in the KLL sketch that achieved optimal asymptotic behavior. This article investigates multiplicative (1±ε )-error approximations to the rank. Practical motivation for multiplicative error stems from demands to understand the tails of distributions, and hence for sketches to be more accurate near extreme values. The most space-efficient algorithms due to prior work store either O(log(ε²n)/ε²) or O(log³ (εn)/ε ) universe items. We present a randomized sketch storing O(log1.5 (εn)/ε ) items that can (1 ± ε )-approximate the rank of each universe item with high constant probability; this space bound is within an O(√log(εn)) factor of optimal. Our algorithm does not require prior knowledge of the stream length and is fully mergeable, rendering it suitable for parallel and distributed computing environments. [ABSTRACT FROM AUTHOR]

We consider the classical problem of maximizing a monotone submodular function subject to a cardinality constraint, which, due to its numerous applications, has recently been studied in various computational models. We consider a clean multiplayer model that lies between the offline and streaming model, and study it under the aspect of one-way communication complexity. Our model captures the streaming setting (by considering a large number of players), and, in addition, two-player approximation results for it translate into the robust setting. We present tight one-way communication complexity results for our model, which, due to the connections mentioned previously, have multiple implications in the data stream and robust setting. Even for just two players, a prior information-theoretic hardness result implies that no approximation factor above 1/2 can be achieved in our model, if only queries to feasible sets (i.e., sets respecting the cardinality constraint) are allowed. We show that the possibility of querying infeasible sets can actually be exploited to beat this bound, by presenting a tight 2/3-approximation taking exponential time, and an efficient 0.514-approximation. To the best of our knowledge, this is the first example where querying a submodular function on infeasible sets leads to provably better results. Through the link to the (non-streaming) robust setting mentioned previously, both of these algorithms improve on the current state of the art for robust submodular maximization, showing that approximation factors beyond 1/2 are possible. Moreover, exploiting the link of our model to streaming, we settle the approximability for streaming algorithms by presenting a tight 1/2 + e hardness result, based on the construction of a new family of coverage functions. This improves on a prior 0.586 hardness and matches, up to an arbitrarily small margin, the best-known approximation algorithm. [ABSTRACT FROM AUTHOR]

We study the computational complexity of (deterministic or randomized) algorithms based on point samples for approximating or integrating functions that can be well approximated by neural networks. Such algorithms (most prominently stochastic gradient descent and its variants) are used extensively in the field of deep learning. One of the most important problems in this field concerns the question of whether it is possible to realize theoretically provable neural network approximation rates by such algorithms. We answer this question in the negative by proving hardness results for the problems of approximation and integration on a novel class of neural network approximation spaces. In particular, our results confirm a conjectured and empirically observed theory-to-practice gap in deep learning. We complement our hardness results by showing that error bounds of a comparable order of convergence are (at least theoretically) achievable. [ABSTRACT FROM AUTHOR]

Motivated by applications in the gig economy, we study approximation algorithms for a sequential pricing problem. The input is a bipartite graph G=(I,J,E) between individuals I and jobs J. The platform has a value of vj for matching job j to an individual worker. In order to find a matching, the platform can consider the edges (ij)∈E in any order and make a one-time take-it-or-leave-it offer of a price πij=w of its choosing to i for completing j. The worker accepts the offer with a known probability pijw; in this case, the job and the worker are irrevocably matched. What is the best way to make offers to maximize revenue and/or social welfare? The optimal algorithm is known to be NP-hard to compute (even if there is only a single job). With this in mind, we design efficient approximations to the optimal policy via a new random-order online contention resolution scheme (RO-OCRS) for matching. Our main result is a 0.456-balanced RO-OCRS in bipartite graphs and a 0.45-balanced RO-OCRS in general graphs. These algorithms improve on the recent bound of 12(1−e−2)≈0.432 and improve on the best-known lower bounds for the correlation gap of matching, despite applying to a significantly more restrictive setting. As a consequence of our online contention resolution scheme results, we obtain a 0.456-approximate algorithm for the sequential pricing problem. We further extend our results to settings where workers can only be contacted a limited number of times and show how to achieve improved results for this problem via improved algorithms for the well-studied stochastic probing problem. Funding: This work was supported by the National Science Foundation [Grant CCF2209520] and a gift from Amazon Research. [ABSTRACT FROM AUTHOR]

Minimizing the weighted completion time of jobs in the unrelated parallel machines model is a fundamental scheduling problem. The first (3 / 2 - c) –approximation algorithm for this problem, for some constant c > 0 , was obtained in the work of Bansal et al. (SIAM J Comput, 2021). A key ingredient in this work was the first dependent-rounding algorithm with a certain guaranteed amount of negative correlation. We improve upon this guaranteed amount from 1/108 to 1/27, thus also improving upon the constant c in the algorithms of Bansal et al. and Li (SIAM J Comput, 2020) for weighted completion time. Given the now-ubiquitous role played by dependent rounding in scheduling and combinatorial optimization, our improved dependent rounding is also of independent interest. [ABSTRACT FROM AUTHOR]

Variational Quantum Algorithms (VQAs) have made great success in the Noisy Intermediate-Scale Quantum (NISQ) era due to their relative resilience to noise and high flexibility relative to quantum resources. Quantum Architecture Search (QAS) aims to enhance the performance of VQAs by refining the structure of the adopted Parameterized Quantum Circuit (PQC). QAS is garnering increased attention owing to its automation, reduced reliance on expert experience, and its ability to achieve better performance while requiring fewer quantum gates than manually designed circuits. However, existing QAS algorithms optimize the structure from scratch for each VQA without using any prior experience, rendering the process inefficient and time-consuming. Moreover, determining the number of quantum gates, a crucial hyper-parameter in these algorithms is a challenging and time-consuming task. To mitigate these challenges, we accelerate the QAS algorithm via a meta-trained generator. The proposed algorithm directly generates high-performance circuits for a new VQA by utilizing a meta-trained Variational AutoEncoder (VAE). The number of quantum gates required in the designed circuit is automatically determined based on meta-knowledge learned from a variety of training tasks. Furthermore, we have developed a meta-predictor to filter out circuits with suboptimal performance, thereby accelerating the algorithm. Simulation results on variational quantum compiling and Quantum Approximation Optimization Algorithm (QAOA) demonstrate the superior performance of our method over a state-of-the-art algorithm, namely Differentiable Quantum Architecture Search (DQAS). [ABSTRACT FROM AUTHOR]

Functionally graded materials are widely used in the aerospace, nuclear, and aviation industries because of their exceptional properties. The progressive and continuous variation in elastic and thermal characteristics across its surfaces reduces thermal stress within the material and increases its endurance. To study how functionally gradient thermoelastic nanobeams interact with abrupt heat in the context of nonclassical thermoelasticity with phase delays, this study introduces a new mathematical model incorporating memory-dependent derivatives. A heat transfer equation based on memory-dependent derivatives with two delay times can be formulated by combining Eringen's assumptions, the Hamiltonian principle, and Euler–Bernoulli's theory. The analytical solutions for the domains of the system were obtained in the field of the Laplace transform. The distributions of physical fields such as temperature, displacement, deflection, and flexural moment were found numerically using an approximation algorithm. Through the discussion of the computational results and the graphical figures, the effects of effective parameters such as kernel functions, time delay, and nonlocal quantum were indicated. Moreover, a comparison of the current thermal conductivity model with existing classical and nonclassical thermal conductivity models was established to confirm the proposed model. [ABSTRACT FROM AUTHOR]

This paper demonstrates that the space of piecewise-smooth bivariate functions can be well-approximated by the space of the functions defined by a set of simple (non-linear) operations on smooth uniform tensor product splines. The examples include bivariate functions with jump discontinuities or normal discontinuities across curves, and even across more involved geometries such as a three-corner discontinuity. The provided data may be uniform or non-uniform, and noisy, and the approximation procedure involves non-linear least-squares minimization. Also included is a basic approximation theorem for functions with jump discontinuity across a smooth curve. [ABSTRACT FROM AUTHOR]

In atmospheric modeling, sub-grid parameterization is an important method for studying the topographic effects of solar radiation using high-resolution Digital Elevation Model (DEM) data. For reducing the amount of computation, some approximate methods that can lead to errors are used in existing sub-grid parameterization schemes for clear-sky direct solar radiation (SPS-CSDSR). The lack of a high-precision fast terrain occlusion algorithm (HPFTOA) remains one of the biggest constraints in this field. This study proposed an HPFTOA. It mainly uses two kinds of acceleration algorithms. One method is to use a dynamic, lossless, and fast occlusion search radius. Another way is to use the rectangular grid for calculations within the accuracy of DEM data to avoid coordinate projection conversions. The test results indicate that the HPFTOA can carry out large-scale computation based on DEM data with a resolution of 90 m. Because it rarely uses approximation algorithms and considers the curvature of the Earth, SPS-CSDSR can achieve unprecedented precision. The HPFTOA can also be used in the fields of mountain solar energy assessment, remote sensing, and telemetry, including terrain-obscuring the probe. As computer performance improves and algorithms and execution code are optimized, the application prospects will be very broad. [ABSTRACT FROM AUTHOR]

Dimension reduction is a technique used to transform data from a high-dimensional space into a lower-dimensional space, aiming to retain as much of the original information as possible. This approach is crucial in many disciplines like engineering, biology, astronomy, and economics. In this paper, we consider the following dimensionality reduction instance: Given an n-dimensional probability distribution p and an integer m < n , we aim to find the m-dimensional probability distribution q that is the closest to p, using the Kullback–Leibler divergence as the measure of closeness. We prove that the problem is strongly NP-hard, and we present an approximation algorithm for it. [ABSTRACT FROM AUTHOR]

We consider the weighted completion time minimization problem for capacitated parallel machines, which is a fundamental problem in modern cloud computing environments. In our setting, the processed jobs may be of varying duration, require different resources, and be of unequal importance (weight). Each server (machine) can process multiple concurrent jobs up to its capacity. We study heuristic approaches with provable approximation guarantees and offer an algorithm that prioritizes the jobs with the smallest volume-by-weight ratio. We bound the algorithm's approximation ratio using a decreasing function of the ratio between the highest resource demand of any job and the server's capacity. Thereafter, we create a hybrid, constant approximation algorithm for two or more machines. We also develop a constant approximation algorithm for the case of a single machine. Via a numerical study and a mixed-integer linear program of the problem, we demonstrate the performance of the suggested algorithm with respect to the optimal solutions and alternative scheduling methods. We show that the suggested scheduling method can be applied to both offline and online problems that may arise in real-world settings. This research is the first, to the best of our knowledge, to propose a polynomial-time algorithm with a constant approximation ratio for minimizing the weighted sum of job completion times for capacitated parallel machines. [ABSTRACT FROM AUTHOR]

Given a graph G = (V, E), a function f: V → {0, 1, 2, 3, 4} is a triple Roman dominating function (TRDF) of G, for each vertex v ∈ V, (i) if f (v) = 0, then v must have either one neighbour in V4, or either two neighbours in V2 ∪ V3 (one neighbour in V3) or either three neighbours in V2, (ii) if f (v) = 1, then v must have either one neighbour in V3 ∪ V4 or either two neighbours in V2, and if f (v) = 2, then v must have one neighbour in V2 ∪ V3 ∪ V4. The triple Roman domination number of G is the minimum weight of an TRDF f of G, where the weight of f is v V f (v). The triple Roman domination problem is to compute the triple Roman domination number of a given graph. In this paper, we study the triple Roman domination problem. We show that the problem is NP-complete for the star convex bipartite and the comb convex bipartite graphs and is APX-complete for graphs of degree at most 4. We propose a linear-time algorithm for computing the triple Roman domination number of proper interval graphs. We also give an (2H (Δ(G) + 1) - 1)-approximation algorithm for solving the problem for any graph G, where Δ(G) is the maximum degree of G and H (d) denotes the first d terms of the harmonic series. In addition, we prove that for any ε > 0 there is no (1/4 - ε) ln |V |-approximation polynomial-time algorithm for solving the problem on bipartite and split graphs, unless NP ⊆ DTIME (|V |O(log log |V |)). [ABSTRACT FROM AUTHOR]

To address the control performance and harmonic suppression issues in maritime vessel rudder permanent magnet servo systems, a fractional-order PID controller was introduced into the existing improved repetitive control strategy. We used the Oustaloup approximation algorithm and particle swarm optimization for tuning the fractional-order PID controller. The optimized parameters substantially improved the control performance. By integrating the fractional-order PID controller with the improved repetitive controller, a composite fractional-order PID repetitive control strategy was formed. Finally, MATLAB/Simulink simulations were conducted to compare and verify the disturbance rejection and harmonic suppression capabilities of the improved control strategy. The results demonstrate its superior control performance, thereby increasing the practicality of the control system in dealing with various situations. [ABSTRACT FROM AUTHOR]

In this paper, the optimal approximation algorithm is proposed to simplify non-linear functions and/or discrete data as piecewise polynomials by using the constrained least squares. In time-sensitive applications or in embedded systems with limited resources, the runtime of the approximate function is as crucial as its accuracy. The proposed algorithm searches for the optimal piecewise polynomial (OPP) with the minimum computational cost while ensuring that the error is below a specified threshold. This was accomplished by using smooth piecewise polynomials with optimal order and numbers of intervals. The computational cost only depended on polynomial complexity, i.e., the order and the number of intervals at runtime function call. In previous studies, the user had to decide one or all of the orders and the number of intervals. In contrast, the OPP approximation algorithm determines both of them. For the optimal approximation, computational costs for all the possible combinations of piecewise polynomials were calculated and tabulated in ascending order for the specific target CPU off-line. Each combination was optimized through constrained least squares and the random selection method for the given sample points. Afterward, whether the approximation error was below the predetermined value was examined. When the error was permissible, the combination was selected as the optimal approximation, or the next combination was examined. To verify the performance, several representative functions were examined and analyzed. [ABSTRACT FROM AUTHOR]

Personalized travel itinerary recommendation algorithms are the focus of research in smart tourism and tourism GIS. Aiming to address issues present in travel itinerary recommendations for the increasingly popular "self-drive tour" mode, this study proposes an algorithm based on comprehensive tourist satisfaction to mitigate problems such as the neglect of important relevant factors and low degree of personalization. First, we construct a model of tourist satisfaction for travel itineraries by comprehensively considering factors including time utilization, the attractiveness of attractions, itinerary feasibility, and the diversity of attraction types. Unlike previous studies, we consider dining and accommodation time during the itinerary, the physical condition of tourists, and the diversity of attraction types, and establish penalty functions to flexibly constrain deviations from the expected conditions in itinerary planning. Then, with the optimization of comprehensive tourist satisfaction as the objective, we design a new algorithm to address the itinerary recommendation problem, supporting tourists in selecting must-visit attractions, restaurants, and hotels, as well as personalized preferences such as the sightseeing sequence. The experimental results demonstrate that our proposed algorithm outperforms two baseline algorithms, providing higher comprehensive tourist satisfaction while also exhibiting greater feasibility in itinerary planning. The proposed algorithm effectively addresses the issue of personalized travel itinerary recommendation, presenting an efficient, feasible, and practical solution. [ABSTRACT FROM AUTHOR]

In this paper, a joint optimization algorithm of offloading decision, energy harvesting time, and unmanned aerial vehicle (UAV) location is proposed for user equipment (UEs)'s task completion latency problem in a communication–sensing–computing integration scenario with wireless energy supply. Under the constraints of causality of energy harvesting consumption by the UEs and conditional mutual information, the total latency minimization problem of the UEs is established. Firstly, the optimization variables of the problem are transformed from three variables of offloading decision, energy harvesting time, and UAV location to two variables of offloading decision and UAV location by means of the derived closed expression, and then the transformed optimization problem is decomposed into the offloading decision optimization sub-problem and the UAV location optimization sub-problem to be solved alternately and iteratively. The genetic algorithm is employed to tackle the optimization sub-problem of offloading decisions, and the successive convex approximation algorithm is applied to the drone positioning optimization sub-problem. Simulation results show that the proposed algorithm in this paper reduces the average task completion latency by 35 percent and 15 percent, respectively, compared to the two baseline algorithms for different numbers of UEs. [ABSTRACT FROM AUTHOR]

We study the synchronization properties of a generic networked dynamical system, and show that, under a suitable approximation, the transition to synchronization can be predicted with the only help of eigenvalues and eigenvectors of the graph Laplacian matrix. The transition comes out to be made of a well defined sequence of events, each of which corresponds to a specific clustered state. The network's nodes involved in each of the clusters can be identified, and the value of the coupling strength at which the events are taking place can be approximately ascertained. Finally, we present large-scale simulations which show the accuracy of the approximation made, and of our predictions in describing the synchronization transition of both synthetic and real-world large size networks, and we even report that the observed sequence of clusters is preserved in heterogeneous networks made of slightly non-identical systems. Natural and synthetic networked systems can be characterized by synchrony or asynchrony of groups of their nodes (clusters) and undergo different scenarios of synchronization transitions. The authors propose an approach to predict the entire sequence of events that are taking place during the synchronization transition in networks of identical elements with any preferrable architecture. [ABSTRACT FROM AUTHOR]

Privacy-preserving neural networks offer a promising solution to train and predict without user privacy leakage, and fully homomorphic encryption (FHE) stands out as one of the key technologies, as it enables homomorphic operations over encrypted data. However, only addition and multiplication homomorphisms are supported by FHE, and thus, it faces huge challenges when implementing non-linear functions with ciphertext inputs. Among the non-linear functions in neural networks, one may refer to the activation function, the argmax function, and maximum pooling. Inspired by using a composition of low-degree minimax polynomials to approximate sign and argmax functions, this study focused on optimizing the homomorphic argmax approximation, where argmax is a mathematical operation that identifies the index of the maximum value within a given set of values. For the method that uses compositions of low-degree minimax polynomials to approximate argmax, in order to further reduce approximation errors and improve computational efficiency, we propose an improved homomorphic argmax approximation algorithm that includes rotation accumulation, tree-structured comparison, normalization, and finalization phases. And then, the proposed homomorphic argmax algorithm was integrated into a neural network structure. Comparative experiments indicate that the network with our proposed argmax algorithm achieved a slight increase in accuracy while significantly reducing the inference latency by 58 % , as the homomorphic sign and rotation operations were rapidly reduced. [ABSTRACT FROM AUTHOR]

When using traditional Euler deconvolution optimization strategies, it is difficult to distinguish between anomalies and their corresponding Euler tails (those solutions are often distributed outside the anomaly source, forming "tail"-shaped spurious solutions, i.e., misplaced Euler solutions, which must be removed or marked) with only the structural index. The nonparametric estimation method based on the normalized B-spline probability density (BSS) is used to separate the Euler solution clusters and mark different anomaly sources according to the similarity and density characteristics of the Euler solutions. For display purposes, the BSS needs to map the samples onto the estimation grid at the points where density will be estimated in order to obtain the probability density distribution. However, if the size of the samples or the estimation grid is too large, this process can lead to high levels of memory consumption and excessive computation times. To address this issue, a fast linear binning approximation algorithm is introduced in the BSS to speed up the computation process and save time. Subsequently, the sample data are quickly projected onto the estimation grid to facilitate the discrete convolution between the grid and the density function using a fast Fourier transform. A method involving multivariate B-spline probability density estimation based on the FFT (BSSFFT), in conjunction with fast linear binning appropriation, is proposed in this paper. The results of two random normal distributions show the correctness of the BSS and BSSFFT algorithms, which is verified via a comparison with the true probability density function (pdf) and Gaussian kernel smoothing estimation algorithms. Then, the Euler solutions of the two synthetic models are analyzed using the BSS and BSSFFT algorithms. The results are consistent with their theoretical values, which verify their correctness regarding Euler solutions. Finally, the BSSFFT is applied to Bishop 5X data, and the numerical results show that the comprehensive analysis of the 3D probability density distributions using the BSSFFT algorithm, derived from the Euler solution subset of  x 0 , y 0 , z 0 , can effectively separate and locate adjacent anomaly sources, demonstrating strong adaptability. [ABSTRACT FROM AUTHOR]

A dominating set of a graph is a subset of vertices such that every vertex not in the subset has at least one neighbor within the subset. The corresponding optimization problem is known to be NP-hard. It is proved to be beneficial to separate the solution process in two stages. First, one can apply a fast greedy algorithm to obtain an initial dominating set and then use an iterative procedure to purify (reduce) the size of this dominating set. In this work, we develop the purification stage and propose new purification algorithms. The purification procedures that we present here outperform, in practice, the earlier known purification procedure. We have tested our algorithms for over 1300 benchmark problem instances. Compared to the estimations due to known upper bounds, the obtained solutions are about seven times better. Remarkably, for the 500 benchmark instances for which the optimum is known, the optimal solutions are obtained for 46.33% of the tested instances, whereas the average error for the remaining instances is about 1.01. [ABSTRACT FROM AUTHOR]

This paper presents an approach to community detection in complex networks by simultaneously incorporating a connectivity-based metric and Max-Min Modularity. By leveraging the connectivity-based metric and employing a heuristic algorithm, we develop a novel complementary graph for the Max-Min Modularity that enhances its effectiveness. We formulate community detection as an integer programming problem of an equivalent yet more compact counterpart model of the revised Max-Min Modularity maximization problem. Using a row generation technique alongside the heuristic approach, we then provide a hybrid procedure for near-optimally solving the model and discovering high-quality communities. Through a series of experiments, we demonstrate the success of our algorithm, showcasing its efficiency in detecting communities, particularly in extensive networks. [ABSTRACT FROM AUTHOR]

Graph coloring is the assignment of one color to each vertex of a graph so that two adjacent vertices are not of the same color. The graph coloring problem (GCP) is a matter of combinatorial optimization, and the goal of GCP is determining the chromatic number (G). Since GCP is an NP-hard problem, then in this paper, we propose a new approximated algorithm for finding the coloring number (it is an approximation of chromatic number) by using a graph adjacency matrix to colorize or separate a graph. To prove the correctness of the proposed algorithm, we implement it in MATLAB software, and for analysis in terms of solution and execution time, we compare our algorithm with some of the best existing algorithms that are already implemented in MATLAB software, and we present the results in tables of various graphs. Several available algorithms used the largest degree selection strategy, while our proposed algorithm uses the graph adjacency matrix to select the vertex that has the smallest degree for coloring. We provide some examples to compare the performance of our algorithm to other available methods. We make use of the Dolan-Moré performance profiles to assess the performance of the numerical algorithms, and demonstrate the efficiency of our proposed approach in comparison with some existing methods. [ABSTRACT FROM AUTHOR]

Experimentation is prevalent in online marketplaces and social networks to assess the effectiveness of new market intervention. To mitigate the interference among users in an experiment, a common practice is to use a cluster-based experiment, where the designer partitions the market into loosely connected clusters and assigns all users in the same cluster to the same variant (treatment or control). Given the experiment, we assume an unbiased Horvitz–Thompson estimator is used to estimate the total market effect of the treatment. We consider the optimization problem of choosing (correlated) randomized assignments of clusters to treatment and control to minimize the worst-case variance of the estimator under a constraint that the marginal assignment probability is q∈(0,1) for all clusters. This problem can be formulated as a linear program where both the number of decision variables and constraints are exponential in the number of clusters—and hence is generally computationally intractable. We develop a family of practical experiments that we refer to as independent block randomization (IBR) experiments. Such an experiment partitions clusters into blocks so that each block contains clusters of similar size. It then treats a fraction q of the clusters in each block (chosen uniformly at random) and does so independently across blocks. The optimal cluster partition can be obtained in a tractable way using dynamic programming. We show that these policies are asymptotically optimal when the number of clusters grows large and no cluster size dominates the rest. In the special case where cluster sizes take values in a finite set and the number of clusters of each size is a fixed proportion of the total number of clusters, the loss is only a constant that is independent of the number of clusters. Beyond the asymptotic regime, we show that the IBR experiment has a good approximation for any problem instance when q is not very tiny. We also examine the performance of the IBR experiments on data-driven numerical examples, including examples based on Airbnb and Facebook data. This paper was accepted by Itai Ashlagi, revenue management and market analytics. Funding: O. Candogan acknowledges NSF [Award 2216912] for "Institute for Data, Econometrics, Algorithms and Learning." Supplemental Material: The online appendix is available at https://doi.org/10.1287/mnsc.2021.02741. [ABSTRACT FROM AUTHOR]

Vegetable oils, which are considered potential lubricants, are composed of different types and proportions of fatty acids. Because of their diverse types and varying compositions, they exhibit different lubrication performances. The genetic function approximation algorithm was used to model the quantitative structure–property relationship between fatty acid structure and the wear scar diameter and friction coefficients measured by four-ball friction and wear tests. Based on the models with adjusted R2 greater than 0.9 and fatty acid compositions of vegetable oils, the wear scar diameter and friction coefficients of Xanthoceras sorbifolia bunge oil and Soybean oil as validation oil samples were predicted. The difference between the predicted and experimental values was small, indicating that the models could accurately predict the lubrication performances of vegetable oils. The lubrication performances of 14 kinds of vegetable oils were predicted by GFA-QSPR models, and the primary factors influencing their lubrication properties were studied by cluster analysis. The results show that the content of C18:1 has a positive effect on the lubrication performances of vegetable oils, while the content of C18:3 has a negative effect, and the length of the carbon chain of fatty acids significantly affects their lubrication properties. [ABSTRACT FROM AUTHOR]

We study two scheduling problems in a proportionate flow shop environment, where job processing times are machine independent. In contrast to classical proportionate flow shop models, we assume (in both problems) that processing times are step-deteriorating. Accordingly, each job J j has a normal processing time, a j , if it starts to be processed in the shop no later than its deteriorating date, δ j . Otherwise, the job's processing time increases by b j (the job's deterioration penalty). Our aim is to find a job schedule that minimizes either the makespan or the total load. These two problems are known to be N P -hard for the special case of a single machine, even when all jobs have the same deteriorating date. In this paper, we derive several positive results in relation to the two problems. We first show that the two problems can be represented in a unified way. We then prove that the unified problem is only ordinary N P -hard by providing a pseudo-polynomial time algorithm for its solution. We also show that the pseudo-polynomial time algorithm can be converted into a fully polynomial time approximation scheme (FPTAS). Finally, we analyze the parameterized complexity of the problem with respect to the number of different deteriorating dates in the instance, v δ . We show that although the problem is N P -hard when v δ = 1 , it is fixed parameterized tractable (FPT) for the combined parameters (i) (ν δ , ν a) and (ii) (ν δ , ν b) , where ν a is the number of different normal processing times in the instance, and ν b is the number of different deterioration penalties in the instance. [ABSTRACT FROM AUTHOR]

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

The Susceptible–Infected–Susceptible (SIS) model in complex networks is one of the critical models employed in the modeling of virus spread. The study of the heterogeneous SIS model with a non-homogeneous nodal infection rate in finite-size networks has attracted little attention. Investigating the statistical properties of heterogeneous SIS epidemic dynamics in finite networks is thus intriguing. In this paper, we focus on the measure of variability in the number of infected nodes for the heterogeneous SIS epidemic dynamics in finite-size bipartite graphs and star graphs. Specifically, we investigate the metastable-state variance of the number of infected nodes for the SIS epidemic process in finite-size bipartite graphs and star graphs with heterogeneous nodal infection rates. We employ an extended individual-based mean-field approximation to analyze the heterogeneous SIS epidemic process in finite-size bipartite networks and star graphs. We derive the approximation solutions of the variance of the infected number. We verify the proposed theory by simulations. The proposed theory has the potential to help us better understand the fluctuations of SIS models like epidemic dynamics with a non-homogeneous infection rate. [ABSTRACT FROM AUTHOR]

This paper develops novel fast numerical solvers for subdiffusion problems with spatial interfaces. These problems are modeled by partial differential equations that contain both fractional order and conventional first order time derivatives. The former is non-local and approximated by L1 and L2 discretizations along with fast evaluation algorithms based on approximation by sums of exponentials. This results in an effective treatment of the "long-tail" kernel of subdiffusion. The latter is local and hence conventional implicit Euler or Crank-Nicolson discretizations can be used. Finite volumes are utilized for spatial discretization based on consideration of local mass conservation. Interface conditions for mass and fractional uxes are incorporated into these fast solvers. Computational complexity and implementation procedures are briey discussed. Numerical experiments demonstrate accuracy and efficiency of these new fast solvers. [ABSTRACT FROM AUTHOR]

This work studies solutions to determine the macro-elastic moduli of three-phase composite materials with imperfect interfaces in 2D. Which is based on the coated circular assemblage model of Hashin-Strikman and the polarization approximation method (PA) to develop the formulae for elastic moduli of circle inclusions with spring-layer and surface-stress imperfect interfaces. From that, explicit algebraic expressions were obtained to estimate the elastic moduli of three-phase composites with imperfect interfaces, in which two phases are different with circular inclusions distributed randomly in the matrix. Besides, the FFT algorithm and the differential approximation (DA) are also developed to determine the elastic moduli of the three-phase composite with imperfect interfaces. The results of the FFT numerical methods will be compared with the DA and PA results with different material cases to show the effectiveness of the applied methods. [ABSTRACT FROM AUTHOR]

This paper considers the problem of finding maximum volume (axis-aligned) inscribed boxes in a compact convex set, defined by a finite number of convex inequalities, and presents optimization and geometric approaches for solving them. Several optimization models are developed that can be easily generalized to find other inscribed geometric shapes such as triangles, rhombi, and squares. To find the largest volume axis-aligned inscribed rectangles in the higher dimensions, an interior-point method algorithm is presented and analyzed. For two-dimensional space, a parametrized optimization approach is developed to find the largest area (axis-aligned) inscribed rectangles in convex sets. The optimization approach provides a uniform framework for solving a wide variety of relevant problems. Finally, two computational geometric (1−ε) –approximation algorithms with sublinear running times are presented that improve the previous results. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms—Continuous. Funding: The author is grateful for the support of Northeastern University for this research. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0239) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0239). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

The Power of Traffic Tolls The paper "In Congestion Games, Taxes Achieve Optimal Approximation" by Paccagnan and Gairing investigates the power and limitations of taxes as interventions in congestion games. Perhaps surprisingly, they find that efficiently computed taxes can achieve the same performance as the best polynomial time algorithm, even when the algorithm has full control over the agents' actions. The authors establish three main results to support this claim. First, they prove that minimizing congestion is NP-hard to approximate within a given factor based on the latency functions. Second, they demonstrate how convex optimization tools can be used to design optimal taxes. Third, they provide a polynomial time algorithm with an approximation factor matching the hardness barrier. The upshot of their contribution can be summarized as follows: Judiciously designed taxes achieve optimal approximation, and no other tractable intervention can improve upon this result. In this work, we address the problem of minimizing social cost in atomic congestion games. For this problem, we present lower bounds on the approximation ratio achievable in polynomial time and demonstrate that efficiently computable taxes result in polynomial time algorithms matching such bounds. Perhaps surprisingly, these results show that indirect interventions, in the form of efficiently computed taxation mechanisms, yield the same performance achievable by the best polynomial time algorithm, even when the latter has full control over the agents' actions. It follows that no other tractable approach geared at incentivizing desirable system behavior can improve upon this result, regardless of whether it is based on taxations, coordination mechanisms, information provision, or any other principle. In short: Judiciously chosen taxes achieve optimal approximation. Three technical contributions underpin this conclusion. First, we show that computing the minimum social cost is NP -hard to approximate within a given factor depending solely on the admissible cost functions. Second, we design a polynomially computable taxation mechanism whose efficiency (price of anarchy) matches this hardness factor, and thus is optimal among all tractable mechanisms. As these results extend to coarse correlated equilibria, any no-regret algorithm inherits the same performances, allowing us to devise polynomial time algorithms with optimal approximation. Supplemental Material: The e-companion is available at https://doi.org/10.1287/opre.2021.0526. [ABSTRACT FROM AUTHOR]

We study a shipment consolidation problem commonly faced by companies that outsource logistics operations and operate in a commit-to-delivery mode. It involves delivering a given set of orders to their destinations by their committed due times using multiple shipping methods at the minimum total shipping and inventory cost. The shipping cost is generally nonlinear in shipping quantity and can be represented by a subadditive piecewise linear function. We investigate two shipping scenarios, one involving long-haul shipping only and the other involving joint long-haul and short-haul shipping. We develop analytical results and solution algorithms for the shipment consolidation problem under each shipping scenario. The problem under the first shipping scenario is shown to be strongly NP -hard. We find that a simple policy, called the First-Due-First-Delivered (FDFD) policy, which assigns orders with earlier delivery due times to shipping methods with earlier destination arrival times, is very effective. This policy enables us to develop a polynomial time algorithm, which not only solves the problem under the concave shipping cost structure optimally but also achieves a performance guarantee of 2 for the problem under the general subadditive shipping cost structure. For the problem under the second shipping scenario, we extend the FDFD policy for long-haul shipping and derive another policy, called the No-Wait policy, for short-haul shipping. We use these policies to develop a polynomial time algorithm and analyze its performance guarantee. Our computational experiments show that the algorithm significantly outperforms a commercial optimization solver, and its performance is robust across different parameter settings that reflect various practical situations. This paper was accepted by Jeannette Song, operations management. Supplemental Material: The data and e-companion are available at https://doi.org/10.1287/mnsc.2023.4835. [ABSTRACT FROM AUTHOR]

Problem definition: Content promotion policies are crucial for online content platforms to improve content consumption and user engagement. However, traditional promotion policies generally neglect the diffusion effect within a crowd of users. In this paper, we study the candidate generation and promotion optimization (CGPO) problem for an online content platform, emphasizing the incorporation of the diffusion effect. Methodology/results: We propose a diffusion model that incorporates platform promotion decisions to characterize the adoption process of online content. Based on this diffusion model, we formulate the CGPO problem as a mixed-integer program with nonconvex and nonlinear constraints, which is proved to be NP-hard. Additionally, we investigate methods for estimating the diffusion model parameters using available online platform data and introduce novel double ordinary least squares (D-OLS) estimators. We prove the submodularity of the objective function for the CGPO problem, which enables us to find an efficient (1−1/e) -approximation greedy solution. Furthermore, we demonstrate that the D-OLS estimators are consistent and have smaller asymptotic variances than traditional ordinary least squares estimators. By utilizing real data from a large-scale video-sharing platform, we show that our diffusion model effectively characterizes the adoption process of online content. Compared with the policy implemented on the platform, our proposed promotion policy increases total adoptions by 49.90%. Managerial implications: Our research highlights the essential role of diffusion in online content and provides actionable insights for online content platforms to optimize their content promotion policies by leveraging our diffusion model. Funding: R. Zhang is grateful for the financial support from the Hong Kong Research Grants Council General Research Fund [Grants 14502722 and 14504123] and the National Natural Science Foundation of China [Grant 72293560/72293565]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2022.0172. [ABSTRACT FROM AUTHOR]

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

We study linear Fisher markets with satiation. In these markets, sellers have earning limits, and buyers have utility limits. Beyond applications in economics, they arise in the context of maximizing Nash social welfare when allocating indivisible items to agents. In contrast to markets with either earning or utility limits, markets with both limits have not been studied before. They turn out to have fundamentally different properties. In general, the existence of competitive equilibria is not guaranteed. We identify a natural property of markets (termed money clearing) that implies existence. We show that the set of equilibria is not always convex, answering a question posed in the literature. We design an FPTAS to compute an approximate equilibrium and prove that the problem of computing an exact equilibrium lies in the complexity class continuous local search (CLS ; i.e., the intersection of polynomial local search (PLS) and polynomial parity arguments on directed graphs (PPAD)). For a constant number of buyers or goods, we give a polynomial-time algorithm to compute an exact equilibrium. We show how (approximate) equilibria can be rounded and provide the first constant-factor approximation algorithm (with a factor of 2.404) for maximizing Nash social welfare when agents have capped linear (also known as budget-additive) valuations. Finally, we significantly improve the approximation hardness for additive valuations to 8/7>1.069. Funding: J. Garg was supported by the National Science Foundation [Grant CCF-1942321 (CAREER)]. M. Hoefer was supported by Deutsche Forschungsgemeinschaft [Grants Ho 3831/5-1, Ho 3831/6-1, and Ho 3831/7-1]. [ABSTRACT FROM AUTHOR]

Router nodes placement (RNP) is an important issue in the design and implementation of wireless mesh networks (WMN). This is known as an P-hard problem, which cannot be solved using conventional algorithms. Consequently, approximate optimization strategies are commonly used to solve this problem. With heavy node density and wide-area WMNs, solving the RNP problem using approximation algorithms often faces many difficulties, therefore, a more effective solution is necessary. This motivated us to conduct this work. We propose a new method for solving the RNP problem using reinforcement learning (RL). The RNP problem is modeled as an RL model with environment, agent, action, and reward are equivalent to the network system, routers, coordinate adjustment, and connectivity of the RNP problem, respectively. To the best of our knowledge, this is the first study that applies RL to solve the RNP problem. The experimental results showed that the proposed method increased the network connectivity by up to 22.73% compared to the most recent methods. [ABSTRACT FROM AUTHOR]

We investigate the seemingly untouched yet the most general parallel identical k-stage flow-shops scheduling, in which we are given an arbitrary number of indistinguishable k-stage flow-shops and a set of jobs each to be processed on one of the flow-shops, and the goal is to schedule these jobs to the flow-shops so as to minimize the makespan. Here the number k of stages is a fixed constant, but the number of flow-shops is part of the input. This scheduling problem is strongly NP-hard. To the best of our knowledge all previously presented approximation algorithms are for the special case where k = 2 , including a 17/6-approximation in 2017, a (2 + ϵ) -approximation in 2018, and the most recent polynomial-time approximation scheme in 2020; they all take advantage of the number of stages being two. We deal with an arbitrary constant k ≥ 3 , where the k-stage flow-shop scheduling is already strongly NP-hard. To define a configuration that summarizes the key information about the job assignments in a feasible schedule, we present novel concepts of big job type, big job assignment pair type, and flow-shop type. We show that the total number of distinct configurations is a polynomial in the input number of flow-shops. We then present how to compute a schedule for each configuration that assigns all the big jobs, followed by how to allocate all the small jobs into the schedule at a cost only a fraction of the makespan. These together lead to a polynomial-time approximation scheme for the problem. [ABSTRACT FROM AUTHOR]

The Skolem problem is a long-standing open problem in linear dynamical systems: can a linear recurrence sequence (LRS) ever reach 0 from a given initial configuration? Similarly, the positivity problem asks whether the LRS stays positive from an initial configuration. Deciding Skolem (or positivity) has been open for half a century: the best known decidability results are for LRS with special properties (e.g., low order recurrences). On the other hand, these problems are much easier for “uninitialised” variants, where the initial configuration is not fixed but can vary arbitrarily: checking if there is an initial configuration from which the LRS stays positive can be decided by polynomial time algorithms (Tiwari in 2004, Braverman in 2006). In this paper, we consider problems that lie between the initialised and uninitialised variants. More precisely, we ask if 0 (resp. negative numbers) can be avoided from every initial configuration in a neighbourhood of a given initial configuration. This can be considered as a robust variant of the Skolem (resp. positivity) problem. We show that these problems lie at the frontier of decidability: if the neighbourhood is given as part of the input, then robust Skolem and robust positivity are Diophantine hard, i.e., solving either would entail major breakthroughs in Diophantine approximations, as happens for (non-robust) positivity. Interestingly, this is the first Diophantine hardness result on a variant of the Skolem problem. On the other hand, if one asks whether such a neighbourhood exists, then the problems turn out to be decidable in their full generality, with PSPACE complexity. Our analysis is based on the set of initial configurations such that positivity holds, which leads to new insights into these difficult problems, and interesting geometrical interpretations. [ABSTRACT FROM AUTHOR]

This paper investigates the potential of active reconfigurable intelligent surfaces (RIS) to enhance wireless-powered communication networks (WPCNs), addressing the evolving connectivity needs of the internet of things (IoT). Active RIS, capable of amplifying and reflecting signals, offers a solution to surpass the limitations of passive RIS, such as double-fading attenuation, aiming to significantly improve network throughput and coverage. Our research focuses on exploiting the amplification capabilities of active RIS to boost the overall network sum throughput, engaging in a comprehensive optimization of critical network parameters, including time allocation, reflection coefficients, and phase shift matrices specific to active RIS. The formulated problem is non-convex and highly complex due to the coupling of optimization variables. We employed a successive convex approximation algorithm to solve the throughput maximization problem by converting the non-convex constraints into approximated convex constraints and solving them iteratively. Through extensive simulations, we demonstrate that our active RIS-assisted network substantially outperforms networks facilitated by passive RIS, marking a significant advancement in WPCN performance. These findings underscore the potential of active RIS technology in realizing the full capabilities of IoT connectivity. [ABSTRACT FROM AUTHOR]

We consider single-machine scheduling with a non-renewable resource. In this setting, we are given a set of jobs, each characterized by a processing time, a weight, and a resource requirement. At fixed points in time, certain amounts of the resource are made available to be consumed by the jobs. The goal is to assign the jobs non-preemptively to time slots on the machine, so that each job has enough resource available at the start of its processing. The objective that we consider is the minimization of the sum of weighted completion times. The main contribution of the paper is a PTAS for the case of 0 processing times ( 1 | r m = 1 , p j = 0 | ∑ w j C j ). In addition, we show strong NP-hardness of the case of unit resource requirements and weights ( 1 | r m = 1 , a j = 1 | ∑ C j ), thus answering an open question of Györgyi and Kis. We also prove that the schedule corresponding to the Shortest Processing Time First ordering provides a 3/2-approximation for the latter problem. Finally, we investigate a variant of the problem where processing times are 0 and the resource arrival times are unknown. We present a (4 + ϵ) -approximation algorithm, together with a (4 - ε) -inapproximability result, for any ε > 0 . [ABSTRACT FROM AUTHOR]

In solving the whole process of interaction between soft rock and yielding support in high-stress environments in tunnels using mechanical analysis methods, it is challenging to simultaneously satisfy both displacement coordination and static equilibrium at the contact surface between the rock and the support structure. This paper, based on the mechanical analysis of rock and rigid support, considers the impact of the circumferential installation of yielding elements on radial displacement, and proposes displacement approximation and support force approximation methods using displacement coordination and static equilibrium as approximation conditions. The study fits curves of numerical simulation results and laboratory test results of yielding elements, and attempts to directly use the laboratory test data set of yielding elements as computational data. By calculating two circular tunnel examples and comparing the effects of the trisection method, bisection method, and substitution method on the convergence of the displacement approximation method, the effectiveness of the methods proposed in this paper is verified. The research results show that the two approximation algorithms proposed in this paper have good accuracy and reliability in calculating the relative displacement of rock and yielding support structure contact surfaces, and the support force of yielding support. The bisection method outperforms the trisection and substitution methods in terms of stability and convergence. However, there are certain limitations in this study, such as the effectiveness of the algorithm may be influenced by geological conditions; the complexity of actual geological conditions may exceed the assumptions of the current rock-support mechanical analysis model. [ABSTRACT FROM AUTHOR]

Theoretical studies on evolutionary algorithms have developed vigorously in recent years. Many such algorithms have theoretical guarantees in both running time and approximation ratio. Some approximation mechanism seems to be inherently embedded in many evolutionary algorithms. In this paper, we identify such a relation by proposing a unified analysis framework for a global simple multiobjective evolutionary algorithm (GSEMO) and apply it on a minimum weight general cover problem, which is general enough to subsume many important problems including the minimum submodular cover problem in which the submodular function is real-valued, and the minimum connected dominating set problem for which the potential function is nonsubmodular. We show that GSEMO yields theoretically guaranteed approximation ratios matching those achievable by a greedy algorithm in expected polynomial time when the potential function g is polynomial in the input size and the minimum gap between different g-values is a constant. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported by National Natural Science Foundation of China [11771013, U20A2068]; Zhejiang Provincial Natural Science Foundation of China [LD19A010001]. [ABSTRACT FROM AUTHOR]