Search

In modern manufacturing and service industries, urgent orders and service tasks are common, and the speed of handling such urgent tasks is an important indicator of production and service efficiency. In this study, we consider scheduling jobs on two parallel machines with the random arrival of an emergency job. The objective is to minimise the makespan, subject to a given maximum waiting time of the emergency job. We first show that the worst-case ratio of the existing algorithm LPT $ _l $ l -SPT $ _{m-l} $ m − l is at least 3/2 when m = 2. We then analyse some properties of the optimal schedule and derive lower bounds on the optimal makespan. Finally, we present an improved approximation algorithm with a tight worst-case ratio of 4/3. We also provide numerical results showing that our proposed algorithm outperforms algorithm LPT $ _l $ l -SPT $ _{m-l} $ m − l . [ABSTRACT FROM AUTHOR]

Drones are increasingly used for last-mile delivery due to their speed and cost-effectiveness. This study focuses on a novel locker-drone delivery system, where trucks transport parcels from the warehouse to lockers, and drones complete the final delivery. This system is ideal for community and intra-facility logistics. The research optimises the network design by determining the location of lockers, the number of drones at each locker, and the assignment of demands to lockers, minimising operating costs. Both single-parcel and multi-parcel capacity drones are examined. We build an optimisation model for each system, considering drone service capacity as a critical constraint. We design an algorithm combining average sample approximation and a genetic algorithm to address demand uncertainty. The algorithm's efficiency is validated through comparative analysis with Gurobi. Numerical experiments, using real and generated data, optimise the network design. Results show that the multi-capacity drone system requires fewer lockers and drones than the singlecapacity system. Although the single-capacity system yields lower drone delivery costs, it incurs higher truck delivery costs. Additionally, a comprehensive cost analysis compares the cost-efficiency of the locker-drone system with a conventional drone delivery system, revealing the cost-saving advantage of the locker-drone system. [ABSTRACT FROM AUTHOR]

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.

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]

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]

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]

Correlation clustering problem (CorCP) is a classical clustering problem, which clusters data based on the similarity of data set, and has many applications in interaction networks, cross-lingual link detection, and communication networks, etc. In this paper, we study a practical generalization of the CorCP, called the capacitated correlation clustering problem (the capacitated CorCP), by constructing a labeled complete graph. On this labeled complete graph, each vertex represents a piece of data. If two pieces of data are similar, then the edge between the corresponding vertices is marked by a positive label +. Otherwise, this edge is marked by a negative label -. The objective of the capacitated CorCP is to group some similar data sets into one cluster as far as possible, while satisfying the cluster capacity constraint. To achieve this objective, we shall partition the vertex set of the labeled complete graph into several clusters, each cluster's size subjecting to an upper bound, so as to minimize the number of disagreements. Here the number of disagreements is defined as the total number of the edges with positive labels between clusters and the edges with negative labels within clusters. Different with the previous algorithm in [18], which subjects to the constraint on the cluster size by a penalty measure, we design an algorithm for the capacitated CorCP to directly output a feasible solution by iteratively constructing clusters based on a preset threshold. Through carefully setting the threshold and sophisticatedly analyzing, our algorithm is proved to have an improved approximation ratio of 5.37. In addition, we also conduct a series of numerical experiments to demonstrate the effectiveness of our algorithm. [ABSTRACT FROM AUTHOR]

Given a set of h pairwise disjoint convex polygonal obstacles in the plane, defined with n vertices, we preprocess and compute one routing table at each vertex in a subset of vertices of . For routing a packet from any vertex s ∈ to any vertex t ∈ , our scheme computes a routing path with a multiplicative stretch 1 + and an additive stretch 2 k ℓ , by consulting routing tables at only a subset of vertices along that path. Here, k is the number of obstacles of the routing path intersects, and ℓ depends on the geometry of obstacles in . During the preprocessing phase, we construct routing tables of size O (n + h 3 2 polylog (h )) in O (n + h 3 2 polylog (h )) time, where < 1 is an input parameter. [ABSTRACT FROM AUTHOR]

We show that, for planar point sets, the number of non-crossing Hamiltonian paths is polynomially bounded in the number of non-crossing paths, and the number of non-crossing Hamiltonian cycles (polygonalizations) is polynomially bounded in the number of surrounding cycles. As a consequence, we can list the non-crossing Hamiltonian paths or the polygonalizations, in time polynomial in the output size, by filtering the output of simple backtracking algorithms for non-crossing paths or surrounding cycles respectively. We do not assume that the points are in general position. To prove these results we relate the numbers of non-crossing structures to two easily-computed parameters of the point set: the minimum number of points whose removal results in a collinear set, and the number of points interior to the convex hull. These relations also lead to polynomial-time approximation algorithms for the numbers of structures of all four types, accurate to within a constant factor of the logarithm of these numbers. [ABSTRACT FROM AUTHOR]

The two-watchman route problem is that of computing a pair of closed tours in an environment so that the two tours together see the whole environment and some length measure on the two tours is minimized. Two standard measures are: the minmax measure, where we want the tours where the longest of them has smallest length, and the minsum measure, where we want the tours for which the sum of their lengths is the smallest. It is known that computing a minmax two-watchman route is NP-hard for simple rectilinear polygons and thus also for simple polygons. Also, any c-approximation algorithm for the minmax two-watchman route is automatically a 2c-approximation algorithm for the minsum two-watchman route. We exhibit two constant factor approximation algorithms for computing minmax two-watchman routes in simple polygons with approximation factors 5.969 and 11.939, having running times O (n 8) and O (n 4) respectively, where n is the number of vertices of the polygon. We also use the same techniques to obtain a 6.922-approximation for the fixed two-watchman route problem running in O (n 2) time, i.e., when two starting points of the two tours are given as input. [ABSTRACT FROM AUTHOR]

In this paper we consider the following problem: Given a Hamiltonian graph G, and a Hamiltonian cycle C of G, can we compute a second Hamiltonian cycle C ′ ≠ C of G, and if yes, how quickly? If the input graph G satisfies certain conditions (e.g. if every vertex of G is odd, or if the minimum degree is large enough), it is known that such a second Hamiltonian cycle always exists. Despite substantial efforts, no subexponential-time algorithm is known for this problem. In this paper we relax the problem of computing a second Hamiltonian cycle in two ways. First, we consider approximating the length of a second longest cycle on n-vertex graphs with minimum degree δ and maximum degree Δ . We provide a linear-time algorithm for computing a cycle C ′ ≠ C of length at least n - 4 α (n + 2 α) + 8 , where α = Δ - 2 δ - 2 . This results provides a constructive proof of a recent result by Girão, Kittipassorn, and Narayanan in the regime of Δ δ = o (n) . Our second relaxation of the problem is probabilistic. We propose a randomized algorithm which computes a second Hamiltonian cycle with high probability, given that the input graph G has a large enough minimum degree. More specifically, we prove that for every 0 < p ≤ 0.02 , if the minimum degree of G is at least 8 p log 8 n + 4 , then a second Hamiltonian cycle can be computed with probability at least 1 - 1 n 50 p 4 + 1 in p o l y (n) · 2 4 p n time. This result implies that, when the minimum degree δ is sufficiently large, we can compute with high probability a second Hamiltonian cycle faster than any known deterministic algorithm. In particular, when δ = ω (log n) , our probabilistic algorithm works in 2 o (n) time. [ABSTRACT FROM AUTHOR]

In this study, we investigate a class of linear multiplicative programs with positive exponents. By introducing p additional variables, the original problem is reformulated into an equivalent problem (EP) within the output space. Subsequently, a novel global optimization algorithm is introduced to tackle EP. The algorithm primarily leverages two key techniques. One is the outer approximation technique, which tightens the relaxed feasible region of EP and improves the upper bound by carefully examining suitable feasible points. The other is the branch and bound technique to guarantee the global optimality of the solution. Numerical results confirm the effectiveness and practicality of the proposed algorithm, thereby underscoring its potential for real-world applications. [ABSTRACT FROM AUTHOR]

Inter-Domain Path Computation under Node-Defined Domain Uniqueness Constraint (IDPC-NDU) is one of the routing cost optimization problems in multi-domain networks that has been proposed and received much attention by researchers. Because the IDPC-NDU is NP-Hard, the approaches using approximation algorithms are frequently used. These approximation algorithms often construct solutions based on connecting edges between adjacent domains, with little consideration of edges between non-adjacent domains. Furthermore, this study investigates how to combine an algorithm with the capability of exploration with another algorithm with the capability of exploiting in order to balance the ability to explore and exploit the search space. As a result, based on new encoding and decoding solution methods, this study proposes combinations of the algorithms Multi-start Method and Variable Neighbourhood Search Method. By considering the inter-domain edges connecting non-adjacent domains, the new encoding and decoding methods help to examine more possible paths between the source node and the destination node. The proposed algorithm is evaluated by comparing it to the most recent algorithms that were proposed to solve the IDPC-NDU. Analysis of experimental results on various instances shows that the proposed algorithm exceeds other algorithms in most of the experimental cases. In particular, one-fifth of the test cases on which the proposed algorithm finds the optimal solution. Besides, the study also analyses the influence of the attributes of the input data on the efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]

This paper proposes an algorithm to obtain the sampling factors to model any frequency partitioning so that it is realized using low complexity rational decimated non-uniform filter banks (RDNUFBs). The proposed algorithm is employed to approximate the Bark scale to find a rational frequency partitioning that can be realized using RDNUFBs with less approximation error. The proposed Bark frequency partitioning is found to reduce the average deviation in centre frequency and bandwidth by 65.04% and 48.50%, respectively, and root-mean-square bandwidth deviation by 54.46% when compared to those of the existing perceptual wavelet approximation of Bark scale. In the first filter bank design approach discussed in the paper, a near-perfect reconstruction partially cosine modulated filter bank is employed to obtain the improved Bark frequency partitioning. In the second design approach, the hardware complexity of the PCM-based RDNUFB is reduced by deriving the channels with different sampling factors from the same prototype filter by the method of channel merging. There is a considerable reduction of 40.83% in the number of multipliers when merging of partially cosine modulated channels is employed. It is also found that both the proposed approaches can reduce the delay by 95.17% when compared to the existing rational tree approximation methods and hence, are suitable for real-time applications. [ABSTRACT FROM AUTHOR]

To address the challenges of efficient hardware design for error-tolerant applications, several techniques of applied approximate computing have been proposed. Pruning algorithms aim to approximate circuits with reduced design requirements at the cost of an acceptable degradation of their quality of result. In this letter, we present the effects of resynthesis, an iterative application of logic synthesis along with pruning algorithms, into a state-of-the-art approximate design flow, AxLS. Resynthesis strategy improves the approximation, achieving up to 70% area-power savings for the same error in the output, and reducing the number of iterations, and hence the time required to explore the design space in up to $30\times $ , to obtain an approximated design. [ABSTRACT FROM AUTHOR]

This research centers on the application of the discrete-time Taylor–Fourier transform (DTTFT) algorithmic implementation for phasor estimation on a field-programmable gate array board. The system employs a finite impulse response structure of a digital Taylor–Fourier filter to extract amplitude and phase information. The hardware description utilizes a multiply accumulator architecture with only forty embedded 9-bit multiplier elements, achieving an 18-bit input–output resolution. Performance assessment involves signal analysis through FPGA-in-the-loop simulation in MATLAB/Simulink. Findings demonstrate that the DTTFT-based phasor estimator can be effectively characterized using VHDL code and implemented on an Intel D2-115 board. [ABSTRACT FROM AUTHOR]

In recent years, the difference-of-convex (DC) optimization has been successfully applied to real-world problems, including signal recovery and image processing. In this paper, we apply a special case of DC optimization, l1 - l2 optimization, to the application of function approximation. Using the sparsity-promoting property of l1 - l2 optimization, we aim to extract an approximation of an unknown function with parsimonious terms from random features. Using concentration inequalities of random variables, we derive a probabilistic error bound for a certain class of functions. From approximation experiments on both synthetic and real datasets, we demonstrate that the proposed optimization outperforms the benchmark algorithm in the aspect of approximation accuracy and robustness to randomness. [ABSTRACT FROM AUTHOR]

A λ $\lambda $‐backbone coloring of a graph G $G$ with its subgraph (also called a backbone) H $H$ is a function c:V(G)→{1,...,k} $c:V(G)\to \{1,\ldots ,k\}$ ensuring that c $c$ is a proper coloring of G $G$ and for each {u,v}∈E(H) $\{u,v\}\in E(H)$ it holds that |c(u)−c(v)|≥λ $|c(u)-c(v)|\ge \lambda $. In this paper we propose a way to color cliques with tree and forest backbones in linear time that the largest color does not exceed max{n,2λ}+Δ(H)2⌈logn⌉ $\max \{n,2\lambda \}+{\rm{\Delta }}{(H)}^{2}\lceil \mathrm{log}n\rceil $. This result improves on the previously existing approximation algorithms as it is (Δ(H)2⌈logn⌉) $({\rm{\Delta }}{(H)}^{2}\lceil \mathrm{log}n\rceil)$‐absolutely approximate, that is, with an additive error over the optimum. We also present an infinite family of trees T $T$ with Δ(T)=3 ${\rm{\Delta }}(T)=3$ for which the coloring of cliques with backbones T $T$ requires at least max{n,2λ}+Ω(logn) $\max \{n,2\lambda \}+{\rm{\Omega }}(\mathrm{log}n)$ colors for λ $\lambda $ close to n2 $\frac{n}{2}$. The construction draws on the theory of Fibonacci numbers, particularly on Zeckendorf representations. [ABSTRACT FROM AUTHOR]

Tang–Gong interleaved sequences constructed from the generalized GMW sequence pair are a class of binary sequences with optimal autocorrelation magnitude. In this paper, the symmetric 2-adic complexity of these sequences is investigated. We first derive a lower bound on their 2-adic complexity by extending the method proposed by Hu. Then, by analysing the algebraic structure of these sequences, a lower bound on their symmetric 2-adic complexity is obtained. Our result shows that the symmetric 2-adic complexity of these sequences is large enough to resist attacks with the rational approximation algorithm. [ABSTRACT FROM AUTHOR]

We study the interplay between the data distribution and Q-learning-based algorithms with function approximation. We provide a unified theoretical and empirical analysis as to how different properties of the data distribution influence the performance of Q-learning-based algorithms. We connect different lines of research, as well as validate and extend previous results, being primarily focused on offline settings. First, we analyze the impact of the data distribution by using optimization as a tool to better understand which data distributions yield low concentrability coefficients. We motivate high-entropy distributions from a game-theoretical point of view and propose an algorithm to find the optimal data distribution from the point of view of concentrability. Second, from an empirical perspective, we introduce a novel four-state MDP specifically tailored to highlight the impact of the data distribution in the performance of Q-learning-based algorithms with function approximation. Finally, we experimentally assess the impact of the data distribution properties on the performance of two offline Q-learning-based algorithms under different environments. Our results attest to the importance of different properties of the data distribution such as entropy, coverage, and data quality (closeness to optimal policy). [ABSTRACT FROM AUTHOR]

This paper studies a two-agent scheduling problem on a single batch machine. Each job j has a processing time pj and a size sj. Jobs should be delivered to the agent as soon as possible. The objective is to minimize the service span of the first agent subject to an upper bound on the makespan of the other agent. We propose two approximation algorithms when jobs have identical processing times and in the general case. Then we conduct theoretical analyses to provide the provable guarantees on the performances of the algorithms. Finally, we conduct simulation analyses based on randomly generated instances to evaluate the average performances of the algorithm in the general case. [ABSTRACT FROM AUTHOR]

The Connectivity Augmentation Problem (CAP) together with a well-known special case thereof known as the Tree Augmentation Problem (TAP) are among the most basic Network Design problems. There has been a surge of interest recently to find approximation algorithms with guarantees below 2 for both TAP and CAP, culminating in the currently best approximation factor for both problems of 1.393 through quite sophisticated techniques. We present a new and arguably simple matching-based method for the well-known special case of leaf-to-leaf instances. Combining our work with prior techniques, we readily obtain a (4 / 3 + ε) -approximation for Leaf-to-Leaf CAP by returning the better of our solution and one of an existing method. Prior to our work, a 4 / 3 -guarantee was only known for Leaf-to-Leaf TAP instances on trees of height 2. Moreover, when combining our technique with a recently introduced stack analysis approach, which is part of the above-mentioned 1.393-approximation, we can further improve the approximation factor to 1.29, obtaining for the first time a factor below 4 3 for a nontrivial class of TAP/CAP instances. [ABSTRACT FROM AUTHOR]

A novel and efficient modeling approach has been developed for simulating the responses of triaxial induction logging (TIL) in layered biaxial anisotropic (BA) formations. The core of this innovative technique lies in analytically calculating the primary fields within a homogeneous medium and approximating the scattered fields within layered formations. The former involves employing a two-level subtraction technique. Initially, the first-level subtraction entails altering the direction of the Fourier transform to mitigate the integral singularity of the spectral fields, particularly in high-angle and horizontal wells. Conversely, the second-level subtraction aims to further optimize integral convergence by creating an equivalent unbounded transverse isotropic (TI) formation and eliminating the corresponding spectral fields. With the two-level subtractions, the convergence of the spectral field has been enhanced by more than six orders of magnitude. Additionally, a strict recursive algorithm and approximation method are developed to compute the scattered fields in layered biaxial anisotropic media. The rigorous algorithm is based on a modified amplitude propagator matrix (MAPM) approach and serves as the benchmark for the approximation method. In contrast, the approximation method exploits the similarity between the spectral scattered field of the TI medium and the BA medium, establishing corresponding equivalent layered TI models for each magnetic component. Since the scattered field in TI models only involves a one-dimensional semi-infinite integral, the computational complexity is significantly reduced. Numerical simulation examples demonstrate that the new simulation method is at least two orders of magnitude faster than the current modeling approach while maintaining computational precision error within 0.5%. This significantly improved simulation efficiency provides a solid foundation for expediting the logging data processing. [ABSTRACT FROM AUTHOR]

Optimization of conflicting functions is of paramount importance in decision making, and real world applications frequently involve data that is uncertain or unknown, resulting in multi-objective optimization (MOO) problems of stochastic type. We study the stochastic multi-gradient (SMG) method, seen as an extension of the classical stochastic gradient method for single-objective optimization. At each iteration of the SMG method, a stochastic multi-gradient direction is calculated by solving a quadratic subproblem, and it is shown that this direction is biased even when all individual gradient estimators are unbiased. We establish rates to compute a point in the Pareto front, of order similar to what is known for stochastic gradient in both convex and strongly convex cases. The analysis handles the bias in the multi-gradient and the unknown a priori weights of the limiting Pareto point. The SMG method is framed into a Pareto-front type algorithm for calculating an approximation of the entire Pareto front. The Pareto-front SMG algorithm is capable of robustly determining Pareto fronts for a number of synthetic test problems. One can apply it to any stochastic MOO problem arising from supervised machine learning, and we report results for logistic binary classification where multiple objectives correspond to distinct-sources data groups. [ABSTRACT FROM AUTHOR]

Summary: Large‐scale linear time‐invariant (LTI) dynamical systems are widely used to characterize complicated physical phenomena. Glover developed the Hankel norm approximation (HNA) algorithm for optimally reducing the system in the Hankel norm, and we study its numerical issues. We provide a remedy for the numerical instabilities of Glover's HNA algorithm caused by clustered singular values. We analyze the effect of our modification on the degree and the Hankel error of the reduced system. Moreover, we propose a two‐stage framework to reduce the order of a large‐scale LTI system given samples of its transfer function for a target degree k$$ k $$ of the reduced system. It combines the adaptive Antoulas–Anderson (AAA) algorithm, modified to produce an intermediate LTI system in a numerically stable way, and the modified HNA algorithm. A carefully computed rational approximation of an adaptively chosen degree d$$ d $$ gives us an algorithm for reducing an LTI system, which achieves a balance between speed and accuracy. [ABSTRACT FROM AUTHOR]

Reoptimization is a setting in which we are given a good approximate solution of an optimization problem instance and a local modification that slightly changes the instance. The main goal is that of finding a good approximate solution of the modified instance. We investigate one of the most studied scenarios in reoptimization known as Steiner tree reoptimization. Steiner tree reoptimization is a collection of strongly NP -hard optimization problems that are defined on top of the classical Steiner tree problem and for which several constant-factor approximation algorithms have been designed in the last decades. In this paper we improve upon all these results by developing a novel technique that allows us to design polynomial-time approximation schemes. Remarkably, prior to this paper, no approximation algorithm better than recomputing a solution from scratch was known for the elusive scenario in which the cost of a single edge decreases. Our results are best possible since none of the problems addressed in this paper admits a fully polynomial-time approximation scheme, unless P = NP [ABSTRACT FROM AUTHOR]

Parameterization above (or below) a guarantee is a successful concept in parameterized algorithms. The idea is that many computational problems admit "natural" guarantees bringing to algorithmic questions whether a better solution (above the guarantee) could be obtained efficiently. For example, for every boolean CNF formula on m clauses, there is an assignment that satisfies at least m/2 clauses. How difficult is it to decide whether there is an assignment satisfying more than m / 2 + k clauses? Or, if an n-vertex graph has a perfect matching, then its vertex cover is at least n/2. Is there a vertex cover of size at least n / 2 + k for some k ≥ 1 and how difficult is it to find such a vertex cover? The above guarantee paradigm has led to several exciting discoveries in the areas of parameterized algorithms and kernelization. We argue that this paradigm could bring forth fresh perspectives on well-studied problems in approximation algorithms. Our example is the longest cycle problem. One of the oldest results in extremal combinatorics is the celebrated Dirac's theorem from 1952. Dirac's theorem provides the following guarantee on the length of the longest cycle: for every 2-connected n-vertex graph G with minimum degree δ (G) ≤ n / 2 , the length of a longest cycle L is at least 2 δ (G) . Thus the "essential" part in finding the longest cycle is in approximating the "offset" k = L - 2 δ (G) . The main result of this paper is the above-guarantee approximation theorem for k. Informally, the theorem says that approximating the offset k is not harder than approximating the total length L of a cycle. In other words, for any (reasonably well-behaved) function f, a polynomial time algorithm constructing a cycle of length f(L) in an undirected graph with a cycle of length L, yields a polynomial time algorithm constructing a cycle of length 2 δ (G) + Ω (f (k)) . [ABSTRACT FROM AUTHOR]

Given a graph, the general problem to cover the maximum number of vertices by a collection of vertex-disjoint long paths seems to escape from the literature. A path containing at least k vertices is considered long. When k ≤ 3 , the problem is polynomial time solvable; when k is the total number of vertices, the problem reduces to the Hamiltonian path problem, which is NP-complete. For a fixed k ≥ 4 , the problem is NP-hard and the best known approximation algorithm for the weighted set packing problem implies a k-approximation algorithm. To the best of our knowledge, there is no approximation algorithm directly designed for the general problem; when k = 4 , the problem admits a 4-approximation algorithm which was presented recently. We propose the first (0.4394 k + O (1)) -approximation algorithm for the general problem and an improved 2-approximation algorithm when k = 4 . Both algorithms are based on local improvement, and their theoretical performance analyses are done via amortization and their practical performance is examined through simulation studies. [ABSTRACT FROM AUTHOR]

k-center is one of the most popular clustering models. While it admits a simple 2-approximation in polynomial time in general metrics, the Euclidean version is NP-hard to approximate within a factor of 1.82, even in the plane, if one insists the dependence on k in the running time be polynomial. Without this restriction, a classic algorithm by Agarwal and Procopiuc [Algorithmica 2002] yields an O (n log k) + (1 / ϵ) O (2 d k 1 - 1 / d log k) -time (1 + ϵ) -approximation for Euclidean k-center, where d is the dimension. We show for a closely related problem, k-supplier, the double-exponential dependence on dimension is unavoidable if one hopes to have a sub-linear dependence on k in the exponent. We also derive similar algorithmic results to the ones by Agarwal and Procopiuc for both k-center and k-supplier. We use a relatively new tool, called Voronoi separator, which makes our algorithms and analyses substantially simpler. Furthermore we consider a well-studied generalization of k-center, called Non-uniform k-center (NUkC), where we allow different radii clusters. NUkC is NP-hard to approximate within any factor, even in the Euclidean case. We design a 2 O (k log k) n 2 time 3-approximation for NUkC in general metrics, and a 2 O ((k log k) / ϵ) d n time (1 + ϵ) -approximation for Euclidean NUkC. The latter time bound matches the bound for k-center. [ABSTRACT FROM AUTHOR]

We address long-standing open questions raised by Williamson, Goemans, Vazirani and Mihail pertaining to the design of approximation algorithms for problems in network design via the primal-dual method (Williamson et al. in Combinatorica 15(3):435–454, 1995. https://doi.org/10.1007/BF01299747). Williamson et al. prove an approximation ratio of two for connectivity augmentation problems where the connectivity requirements can be specified by uncrossable functions. They state: "Extending our algorithm to handle non-uncrossable functions remains a challenging open problem. The key feature of uncrossable functions is that there exists an optimal dual solution which is laminar... A larger open issue is to explore further the power of the primal-dual approach for obtaining approximation algorithms for other combinatorial optimization problems." Our main result proves that the primal-dual algorithm of Williamson et al. achieves an approximation ratio of 16 for a class of functions that generalizes the notion of an uncrossable function. There exist instances that can be handled by our methods where none of the optimal dual solutions has a laminar support. We present three applications of our main result to problems in the area of network design. (1) A 16 -approximation algorithm for augmenting a family of small cuts of a graph G. The previous best approximation ratio was O (log | V (G) |) . (2) A 16 · ⌈ k / u min ⌉ -approximation algorithm for the Cap-k-ECSS problem which is as follows: Given an undirected graph G = (V , E) with edge costs c ∈ Q ≥ 0 E and edge capacities u ∈ Z ≥ 0 E , find a minimum-cost subset of the edges F ⊆ E such that the capacity of any cut in (V, F) is at least k; u min (respectively, u max ) denotes the minimum (respectively, maximum) capacity of an edge in E, and w.l.o.g. u max ≤ k . The previous best approximation ratio was min (O (log | V |) , k , 2 u max) . (3) A 20 -approximation algorithm for the model of (p, 2)-Flexible Graph Connectivity. The previous best approximation ratio was O (log | V (G) |) , where G denotes the input graph. [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]

We generalize the celebrated isoperimetric inequality of Khot, Minzer, and Safra (SICOMP 2018) for Boolean functions to the case of real‐valued functions f:{0,1}d→ℝ$$ f:{\left\{0,1\right\}}^d\to \mathbb{R} $$. Our main tool in the proof of the generalized inequality is a new Boolean decomposition that represents every real‐valued function f$$ f $$ over an arbitrary partially ordered domain as a collection of Boolean functions over the same domain, roughly capturing the distance of f$$ f $$ to monotonicity and the structure of violations of f$$ f $$ to monotonicity. We apply our generalized isoperimetric inequality to improve algorithms for testing monotonicity and approximating the distance to monotonicity for real‐valued functions. Our tester for monotonicity has query complexity O˜(min(rd,d))$$ \tilde{O}\left(\min \left(r\sqrt{d},d\right)\right) $$, where r$$ r $$ is the size of the image of the input function. (The best previously known tester makes O(d)$$ O(d) $$ queries, as shown by Chakrabarty and Seshadhri (STOC 2013).) Our tester is nonadaptive and has 1‐sided error. We prove a matching lower bound for nonadaptive, 1‐sided error testers for monotonicity. We also show that the distance to monotonicity of real‐valued functions that are α$$ \alpha $$‐far from monotone can be approximated nonadaptively within a factor of O(dlogd)$$ O\left(\sqrt{d\log d}\right) $$ with query complexity polynomial in 1/α$$ 1/\alpha $$ and the dimension d$$ d $$. This query complexity is nearly optimal for nonadaptive algorithms even for the special case of Boolean functions (The best previously known distance approximation algorithm for real‐valued functions, by Fattal and Ron (TALG 2010) achieves O(dlogr)$$ O\left(d\log r\right) $$‐approximation.). [ABSTRACT FROM AUTHOR]

In this study, we propose a novel cloud-edge collaborative task assignment model for smart farms that consists of a cloud server, m edge servers, and n sensors. The edge servers rely solely on solar-generated energy, which is limited, whereas the cloud server has access to a limitless amount of energy supplied by the smart grid. Each entire task from a sensor is processed by either an edge server or the cloud server. We consider the task to be unsplittable. Building on the algorithm for the multimachine job scheduling problem, we develop a corresponding approximation algorithm. In addition, we propose a new discrete heuristic based on the dwarf mongoose optimization algorithmm, named the discrete dwarf mongoose optimization algorithm, and we utilize the proposed approximation algorithm to improve the convergence speed of this heuristic while yielding better solutions. In this study, we consider task sets with heavy tasks independently, where a heavy task is a task that requires many computing resources to process. If such tasks are assigned as ordinary tasks, the assignment results may be poor. Therefore, we propose a new method to solve this kind of problem. [ABSTRACT FROM AUTHOR]

The Probabilistic p-Center problem under Pressure (Min PpCP) is a variant of the usual Minp-Center problem we recently introduced in the context of wildfire management. The problem is to locate p shelters minimizing the maximum distance people will have to cover in case of fire in order to reach the closest accessible shelter. The landscape is divided into zones and is modeled as an edge-weighted graph with vertices corresponding to zones and edges corresponding to direct connections between two adjacent zones. The risk associated with fire outbreaks is modeled using a finite set of fire scenarios. Each scenario corresponds to a fire outbreak on a single zone (i.e., on a vertex) with the main consequence of modifying evacuation paths in two ways. First, an evacuation path cannot pass through the vertex on fire. Second, the fact that someone close to the fire may not take rational decisions when selecting a direction to escape is modeled using new kinds of evacuation paths. In this paper, we characterize the set of feasible solutions of Min PpCP-instance. Then, we propose some approximation results for Min PpCP. These results require approximation results for two variants of the (deterministic) Minp-Center problem called Min MACp-Center and Min Partialp-Center. [ABSTRACT FROM AUTHOR]

Due to Prolonged operation and external environmental factors, composite insulators may develop various defects, which can potentially lead to serious accidents in power systems. Detecting and analyzing these defects is critically important. In this study, we combine machine learning with laser‐induced breakdown spectroscopy (LIBS) to identify defects in composite insulators and obtain spectral data from both defective and nondefective samples. The Uniform Manifold Approximation and Projection algorithm was employed to reduce the dimensionality of the data, thereby enhancing detection accuracy and efficiency. Decision tree, random forest (RF), K‐nearest neighbor, and support vector machine algorithms were used to classify the dimensionality‐reduced data. The results indicate that the RF algorithm achieved the best classification performance, with accuracies of 100% and 95.46% for the training and test sets, respectively. Furthermore, the precision, recall, and F1 scores, which reflect model performance, also showed superior results with the RF algorithm. These findings suggest that the combination of LIBS technology and machine learning can rapidly and accurately detect and analyze defects in composite insulators, offering new insights and methods for defect detection in composite insulators. [ABSTRACT FROM AUTHOR]

Confidence bands are used to estimate the likely range of the true parameter, whereas prediction bands provide an idea of the possible values of the parameter after applying a regression model. This study proposes an equation to construct confidence and prediction bands applicable to any linear or nonlinear chemometric regression model; that is, statistical methods used in analytical chemistry to establish relationships between two or more variables. The proposed equation is developed and presented as a useful tool to represent the uncertainty in estimates based on a set of data in chemical measurements. Once the set of data is adjusted as a regression model (linear, polynomial, or multivariable), the proposed equation can be used to construct confidence and prediction bands based on the adjustment equation. The proposed equation operates if the adjustment equation is continuous and derivable. The plot bands on any regression model provide a solid understanding of uncertainty assessment and have the advantage of total control and independence of algorithms and numeral approximations. [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]

In multi-objective mixed-integer convex optimization, multiple convex objective functions need to be optimized simultaneously while some of the variables are restricted to take integer values. In this paper, we present a new algorithm to compute an enclosure of the nondominated set of such optimization problems. More precisely, we decompose the multi-objective mixed-integer convex optimization problem into several multi-objective continuous convex optimization problems, which we refer to as patches. We then dynamically compute and improve coverages of the nondominated sets of those patches to finally combine them to obtain an enclosure of the nondominated set of the multi-objective mixed-integer convex optimization problem. Additionally, we introduce a mechanism to reduce the number of patches that need to be considered in total. Our new algorithm is the first of its kind and guaranteed to return an enclosure of prescribed quality within a finite number of iterations. For selected numerical test instances we compare our new criterion space based approach to other algorithms from the literature and show that much larger instances can be solved with our new algorithm. [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]

We here present CLUES2, a full-likelihood method to infer natural selection from sequence data that is an extension of the method CLUES. We make several substantial improvements to the CLUES method that greatly increases both its applicability and its speed. We add the ability to use ancestral recombination graphs on ancient data as emissions to the underlying hidden Markov model, which enables CLUES2 to use both temporal and linkage information to make estimates of selection coefficients. We also fully implement the ability to estimate distinct selection coefficients in different epochs, which allows for the analysis of changes in selective pressures through time, as well as selection with dominance. In addition, we greatly increase the computational efficiency of CLUES2 over CLUES using several approximations to the forward–backward algorithms and develop a new way to reconstruct historic allele frequencies by integrating over the uncertainty in the estimation of the selection coefficients. We illustrate the accuracy of CLUES2 through extensive simulations and validate the importance sampling framework for integrating over the uncertainty in the inference of gene trees. We also show that CLUES2 is well-calibrated by showing that under the null hypothesis, the distribution of log-likelihood ratios follows a χ 2 distribution with the appropriate degrees of freedom. We run CLUES2 on a set of recently published ancient human data from Western Eurasia and test for evidence of changing selection coefficients through time. We find significant evidence of changing selective pressures in several genes correlated with the introduction of agriculture to Europe and the ensuing dietary and demographic shifts of that time. In particular, our analysis supports previous hypotheses of strong selection on lactase persistence during periods of ancient famines and attenuated selection in more modern periods. [ABSTRACT FROM AUTHOR]

In topology optimization of transient problems, memory requirements and computational costs often become prohibitively large due to the backward‐in‐time adjoint equations. Common approaches such as the Checkpointing (CP) and Local‐in‐Time (LT) algorithms reduce memory requirements by dividing the temporal domain into intervals and by computing sensitivities on one interval at a time. The CP algorithm reduces memory by recomputing state solutions instead of storing them. This leads to a significant increase in computational cost. The LT algorithm introduces approximations in the adjoint solution to reduce memory requirements and leads to a minimal increase in computational effort. However, we show that convergence can be hampered using the LT algorithm due to errors in approximate adjoints. To reduce memory and/or computational time, we present two novel algorithms. The hybrid Checkpointing/Local‐in‐Time (CP/LT) algorithm improves the convergence behavior of the LT algorithm at the cost of an increased computational time but remains more efficient than the CP algorithm. The Parallel‐Local‐in‐Time (PLT) algorithm reduces the computational time through a temporal parallelization in which state and adjoint equations are solved simultaneously on multiple intervals. State and adjoint fields converge concurrently with the design. The effectiveness of each approach is illustrated with two‐dimensional density‐based topology optimization problems involving transient thermal or flow physics. Compared to the other discussed algorithms, we found a significant decrease in computational time for the PLT algorithm. Moreover, we show that under certain conditions, due to the use of approximations in the LT and PLT algorithms, they exhibit a bias toward designs with short characteristic times. Finally, based on the required memory reduction, computational cost, and convergence behavior of optimization problems, guidelines are provided for selecting the appropriate algorithms. [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]