Search

The main results of this paper provide an Efficient Polynomial-Time Approximation Scheme (EPTAS) for approximating the genus (and non-orientable genus) of dense graphs. By dense we mean that \(|E(G)|\ge \alpha \, |V(G)|^2\) for some fixed \(\alpha \gt 0\). While a constant-factor approximation is trivial for this class of graphs, approximations with factor arbitrarily close to 1 need a sophisticated algorithm and complicated mathematical justification. More precisely, we provide an algorithm that for a given (dense) graph G of order n and given \(\varepsilon \gt 0\) , returns an integer g such that G has an embedding in a surface of genus g, and this is ɛ-close to a minimum genus embedding in the sense that the minimum genus \(\mathsf {g}(G)\) of G satisfies: \(\mathsf {g}(G)\le g\le (1+\varepsilon)\mathsf {g}(G)\). The running time of the algorithm is \(O(f(\varepsilon)\,n^2)\) , where \(f(\cdot)\) is an explicit function. Next, we extend this algorithm to also output an embedding (rotation system) whose genus is g. This second algorithm is an Efficient Polynomial-time Randomized Approximation Scheme (EPRAS) and runs in time \(O(f_1(\varepsilon)\,n^2)\). Our algorithms are based on the analysis of minimum genus embeddings of quasirandom graphs. We use a general notion of quasirandom graphs [25]. We start with a regular partition obtained via an algorithmic version of the Szemerédi Regularity Lemma (due to Frieze and Kannan [17] and to Fox, Lovász, and Zhao [14, 15]). We then partition the input graph into a bounded number of quasirandom subgraphs, which are preselected in such a way that they admit embeddings using as many triangles and quadrangles as faces as possible. Here we provide an ɛ-approximation \(\nu (G)\) for the maximum number of edge-disjoint triangles in G. The value \(\nu (G)\) can be computed by solving a linear program whose size is bounded by certain value \(f_2(\varepsilon)\) depending only on ɛ. After solving the linear program, the genus can be approximated (see Corollary 1.7). The proof of this result is long and will be of independent interest in topological graph theory. [ABSTRACT FROM AUTHOR]

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.

Nowadays, maximizing the non-negative and non-submodular objective functions under Knapsack constraint or Cardinality constraint is deeply researched. Nevertheless, few studies study the objective functions with non-submodularity under the non-submodular constraint. And there are many practical applications of the situations, such as Epidemic transmission, and Sensor Placement and Feature Selection problem. In this paper, we study the maximization of the non-submodular objective functions under the non-submodular constraint. Based on the non-submodular constraint, we discuss the maximization of the objective functions with some specific properties, which includes the property of negative, and then, we obtain the corresponding approximate ratios by the greedy algorithm. What is more, these approximate ratios could be improved when the constraint becomes tight. [ABSTRACT FROM AUTHOR]

The utilized research work studies the well-posedness theoretical results and Galerkin-shifted approximations of delay Volterra integrodifferential models of fractional orders and exponential kernels in linear and nonlinear types in the Caputo–Fabrizio sense. Schauder's and Arzela–Ascoli's theorems are employed to prove a local existence theorem. After that, the Laplace continuous transform is employed to establish and confirm the global well-posedness theoretical results for the presented delay model. For numerical solutions, the Legendre–Galerkin shifted approximations' algorithm has been used by the dependence on the orthogonal Legendre shifted polynomials to find out the required approximations. Utilizing this scheme, the considered delay model is reduced to an algebraic system with initial constraints. The algorithm precision, error behavior, and convergence are studied. Several numerical experiments together with several tables and figures are included to present the performance and validation of the algorithm presented. At last, some consequences and notes according to the given consequences were offered in the final section with several suggestions to guide future action. [ABSTRACT FROM AUTHOR]

In this article we prove that the minimum-degree greedy algorithm, with adversarial tie-breaking, is a (2 / 3) -approximation for the Maximum Independent Set problem on interval graphs. We show that this is tight, even on unit interval graphs of maximum degree 3. We show that on chordal graphs, the greedy algorithm is a (1 / 2) -approximation and that this is again tight. These results contrast with the known (tight) approximation ratio of 3 Δ + 2 of the greedy algorithm for general graphs of maximum degree Δ. [ABSTRACT FROM AUTHOR]

In online platforms, the reviews posted by existing consumers are playing an increasingly important role in the purchasing decisions of potential consumers. Motivated by this observation, we study the problems faced by a platform selling a single product with no capacity constraint, where the demand is explicitly influenced by the reviews presented to the consumers. More precisely, we model a consumer's browsing of reviews for a single product as following a cascade click model, with each consumer seeing some initial number of reviews and forming a utility estimate for the product based on the reviews the consumer has read. In the first part of the paper, we consider how to rank the reviews to induce short- and long-term revenue-maximizing purchasing behaviors. In the second part, we study how to set the price of the product. We derive structural insights and bounds on both problems. We also consider the case that the parameters of the model are unknown, where we propose algorithms that learn the parameters and optimize the ranking of the reviews or the price online. We show that our algorithms have regrets O (T 2 3 ). [ABSTRACT FROM AUTHOR]

Motivated by make-to-order applications with committed delivery dates in a variety of industries, we investigate the integrated multi-plant collaborative production, inventory, and hub–spoke delivery problem in a complex production–distribution network. This network includes multi-location heterogeneous plants, distribution centers, and customers, for producing customized and splittable orders with one or more general-size multi-type jobs. Completed jobs are transported from plants to distribution centers, and then the orders whose all constituent jobs have arrived are delivered from distribution centers to customer sites. The objective is to make integrated scheduling decisions for production, inventory, and delivery, for minimizing total cost composed of production, transportation, tardiness, and inventory. We first formulate this problem as a mixed-integer programming model, and analyze its intractability by proving that the problem is NP-hard and no approximation algorithms exist with a constant worst-case ratio. We then reformulate this problem as a binary integer linear programming model to select a feasible schedule for each job, and propose a combined column generation and two-layer column enumeration algorithm to solve it. Through extensive numerical experiments, we demonstrate that our proposed algorithm is capable of generating optimal or near-optimal solutions expeditiously and outperforms four benchmark approaches, and gain valuable managerial insights for practitioners. [ABSTRACT FROM AUTHOR]

To reduce the pressure drop of diesel particulate filter (DPF) as well as improve its collection efficiency. A mathematical model of DPF pressure drop and capture efficiency was established. This research systematically investigates the effects of channels per square inch (CPSI), wall thickness, and carrier ratio on DPF performance through grey relational analysis (GRA) and polynomial approximation algorithm (PAA). The findings reveal that DPF exhibits lower pressure drop and higher collection efficiency in the case where the carrier ratio, wall thickness, and CPSI are within the ranges of 1.40 to 1.53, 9.8 to 10.5 mil, and 200 to 300, respectively. Particularly, at a carrier ratio of 1.52 and a wall thickness of 10.38 mil, the pressure drop reaches a minimum value of 4.23 kPa, with a collection efficiency of 90.28%. Meanwhile, at a carrier ratio of 1.52 and a CPSI of 200, the pressure drop reaches a minimum value of 4.17 kPa, with a collection efficiency of 90.21%. The model expressions for pressure drop and collection efficiency derived from the PAA are: y 1 = 51.19 + 3.815 x 1 − 8.726 x 2 + 3.794 x 1 2 − 1.735 x 1 x 2 + 0.524 x 2 2 , and y 2 = 0.383 + 0.105 x 1 + 0.085 x 2 + 0.032 x 1 2 − 0.016 x 1 x 2 − 0.0032 x 2 2 . The foregoing models exhibit excellent predictive accuracy and goodness of fit for the DPF performance. Under the interactive influence of carrier ratio and wall thickness, the root mean square errors (RMSE) for pressure drop and collection efficiency are 0.0110 and 0.0002, respectively, with corresponding goodness of fit values of 0.9996 and 0.9985. As revealed by the GRA results, wall thickness exerts the most significant impact on DPF performance, presenting a GRG of 0.84 for filtration efficiency and 0.79 for pressure drop. The overall influence on both collection efficiency and pressure drop follows the descending order: wall thickness > carrier ratio > CPSI. This work has important engineering significance for optimizing the DPF capture performance and extending its working time. [ABSTRACT FROM AUTHOR]

We define a new class of set functions that, in addition to being monotone and subadditive, also admit a very limited form of submodularity defined over a permutation of the ground set. We refer to this permutation as a submodular order. This class of functions includes monotone submodular functions as a subfamily. We give fast algorithms with strong approximation guarantees for maximizing submodular order functions under a variety of constraints and show a nearly tight upper bound on the highest approximation guarantee achievable by algorithms with polynomial query complexity. Applying this new notion to the problem of constrained assortment optimization in fundamental choice models, we obtain new algorithms that are both faster and have stronger approximation guarantees (in some cases, first algorithm with constant factor guarantee). We also show an intriguing connection to the maximization of monotone submodular functions in the streaming model, where we recover best known approximation guarantees as a corollary of our results. This paper was accepted by Chung Piaw Teo, optimization. Funding: This work was supported by the NSF Division of Civil, Mechanical, and Manufacturing Innovation [Grant 2340306] and Google Research Scholar Program. Supplemental Material: The online appendices are available at https://doi.org/10.1287/mnsc.2021.04108. [ABSTRACT FROM AUTHOR]

In this paper, we present approximation algorithms for the Airport and Railway problem (AR) on several classes of graphs. The AR problem, introduced as reported by Adamaszek et al. (in: Ollinger, Vollmer (eds) 33rd symposium on theoretical aspects of computer science (STACS 2016). Leibniz international proceedings in informatics (LIPIcs), Dagstuhl, 2016), is a combination of the Capacitated Facility Location problem (CFL) and the Network Design Problem (NDP). An AR instance consists of a set of points (cities) V in a metric d(.,.), each of which is associated with a non-negative cost f v and a number k, which represent respectively the cost of establishing an airport (facility) in the corresponding point, and the universal airport capacity. A feasible solution is a network of airports and railways providing services to all cities without violating any capacity, where railways are edges connecting pairs of points, with their costs equivalent to the distance between the respective points. The objective is to find such a network with the least cost. In other words, find a forest, each component having at most k points and one open facility, minimizing the total cost of edges and airport opening costs. As reported by Adamaszek et al. (in: Ollinger, Vollmer (eds) 33rd symposium on theoretical aspects of computer science (STACS 2016). Leibniz international proceedings in informatics (LIPIcs), Dagstuhl, 2016) presented a PTAS for AR in the two-dimensional Euclidean metric R 2 with a uniform opening cost. In subsequent work (as reported by Adamaszek et al. (in: Niedermeier, Vallée (eds) 35th symposium on theoretical aspects of computer science (STACS 2018). Leibniz international proceedings in informatics (LIPIcs), Dagstuhl, 2018).) presented a bicriteria 4 3 2 + 1 α -approximation algorithm for AR with non-uniform opening costs but violating the airport capacity by a factor of 1 + α , i.e. (1 + α) k capacity where 0 < α ≤ 1 , a 2 + k k - 1 + ε -approximation algorithm and a bicriteria Quasi-Polynomial Time Approximation Scheme (QPTAS) for the same problem in the Euclidean plane R 2 . In this work, we give a 2-approximation for AR with a uniform opening cost for general metrics and an O (log n) -approximation for non-uniform opening costs. We also give a QPTAS for AR with a uniform opening cost in graphs of bounded treewidth and a QPTAS for a slightly relaxed version in the non-uniform setting. The latter implies O(1)-approximation on graphs of bounded doubling dimensions, graphs of bounded highway dimensions and planar graphs in quasi-polynomial time. [ABSTRACT FROM AUTHOR]

In many practical make-to-order production systems, to obtain the profit requirements but with limited resources and delivery requirements, a decision-maker may only accept some of the orders and reject the others, and schedule the accepted orders onto the machines for processing. Meanwhile, accepted jobs (orders) will generate a corresponding profit, and the decision-maker wants to obtain maximum profits. It is common in practical make-to-order production systems that jobs (orders) may have different release dates. In this paper, this scheduling problem is modeled as W-prize-collecting with release dates on a single machine. In this problem, each job is either accepted and processed on a single machine, or is rejected by paying a rejection cost, where each job has a release date and profit. The objective is to minimize the makespan of the accepted jobs plus the total cost of the rejected jobs, conditional on their total profit being no less than a given threshold. It will be proved that the problem is NP-hard for a special case, that is, when the job has the same processing time but no release dates. Furthermore, a 3-approximation algorithm for this problem is also proposed. Then, a pseudo-polynomial time dynamic programming algorithm is provided. Next, based on the dynamic programming algorithm, a fully polynomial time approximation scheme (FPTAS) for this problem is also obtained. Finally, our numerical tests indicate that the dynamic programming algorithm can solve medium-size problems in reasonable running time. [ABSTRACT FROM AUTHOR]

We study the greedy algorithms for m-term approximation. We propose a modification of the Weak Rescaled Pure Greedy Algorithm (WRPGA) — Approximate Weak Rescaled Pure Greedy Algorithm (AWRPGA) — with respect to a dictionary of a Banach space X. By using a geometric property of the unit sphere of X, we obtain a general error estimate in terms of some K-functional. This estimate implies the convergence condition and convergence rate of the AWRPGA. Furthermore, we obtain the corresponding error estimate for the Vector Approximate Weak Rescaled Pure Greedy Algorithm (VAWRPGA). We show that the AWRPGA (VAWRPGA) performs as well as the WRPGA (VWRPGA) when the noise amplitude changes relatively little. Finally, by using the wavelet bases and trigonometric system of Lebesgue spaces, we show that the convergence rate of the AWRPGA is optimal. [ABSTRACT FROM AUTHOR]

Motivated by a transit line planning problem in transportation systems, we investigate the following capacitated assignment problem under a budget constraint. Our model involves L bins and P items. Each bin l has a utilization cost c l and an n l -dimensional capacity vector. Each item p has an n l -dimensional binary weight vector r l p , where the 1s in r l p (if any) appear in consecutive positions, and its assignment to bin l yields a reward v l p. The objective is to maximize total rewards through an assignment that satisfies three constraints: (i) the total weights of assigned items do not violate any bin's capacity; (ii) each item is assigned to at most one open bin; and (iii) the overall utilization costs remain within a total budget B. We propose the first randomized rounding algorithm with a constant approximation ratio for this problem. We then apply our framework to the motivating transit line planning problem, presenting corresponding models and conducting numerical experiments using real-world data. Our results demonstrate significant improvements over previous approaches in addressing this critical transportation challenge. [ABSTRACT FROM AUTHOR]

ABSTRACT This article considers a distributed identification problem for linear stochastic systems whose input and output observations are scheduled by an adaptive event‐triggered scheme. An event detector with time‐varying thresholds is designed to control the transmission of measurements from the sensors to the estimators, which leads to that only a subset of input and output data is available for identification. The estimators exchange information over a network and cooperatively identify the unknown parameters. A distributed recursive identification algorithm under the event‐triggered scheme is proposed based on the distributed stochastic approximation algorithm with expanding truncations (DSAAWET). Under mild assumptions, the strong consistency of the algorithm is proved, that is, the estimates generated from each estimator achieve consensus and converge to the true parameters with probability one. Finally, two numerical examples are provided to validate the theoretical results of the algorithm. [ABSTRACT FROM AUTHOR]

We consider the inverse problem of finding a magnitude-symmetric matrix (matrix with opposing off-diagonal entries equal in magnitude) with a prescribed set of principal minors. This problem is closely related to the theory of recognizing and learning signed determinantal point processes in machine learning, as kernels of these point processes are magnitude-symmetric matrices. In this work, we prove a number of properties regarding sparse and generic magnitude-symmetric matrices. We show that principal minors of order at most ℓ , for some invariant ℓ depending only on principal minors of order at most two, uniquely determine principal minors of all orders. In addition, we produce a polynomial-time algorithm that, given access to principal minors, recovers a matrix with those principal minors using only a quadratic number of queries. Furthermore, when principal minors are known only approximately, we present an algorithm that approximately recovers a matrix, and show that the approximation guarantee of this algorithm cannot be improved in general. [ABSTRACT FROM AUTHOR]

ABSTRACT This article investigates the issue of finite‐time tracking control for uncertain robotic manipulator systems with unknown actuator faults and shifting loads based upon a fuzzy sliding mode control strategy. A novel fuzzy adaptive sliding mode fault‐tolerant control law is synthesized, where a fuzzy approximation algorithm is utilized to fit the unknown plant parameters, potential disturbances, and relational actuator faults, and the corresponding adaptive robust term is designed to estimate the unidentified boundary of the estimated errors, and the boundedness of all the relevant design parameters of the manipulator systems is ensured combining with the average dwell time mechanism of switched system control theory. Furthermore, the reachability of the pre‐devised sliding surface and the finite‐time convergence of tracking error are achieved under the presented controller design. Ultimately, simulation results exhibit the feasibility and superiority of the proposed algorithm. [ABSTRACT FROM AUTHOR]

The paper proposes a viscosity approximation algorithm for approximating fixed points. The study in this paper demonstrates that without having the prior estimations of operator norm and semicompactness of one‐parameter semigroups of nonexpansive mappings, the algorithm converges strongly to the solution of split equality generalized mixed equilibrium problem (SEGMEP). MSC2010 Classification: Primary 47H10, 47H09, 47J05, 47J25, 54H25 [ABSTRACT FROM AUTHOR]

We consider a variant of the offline Dial-a-Ride problem on weighted graphs with a single server where each request has a source and destination. The server's goal is to serve requests so as to maximize the total number of requests served within a given time limit. We first prove that no polynomial-time algorithm will always serve the optimal number of requests, even when the algorithm's time limit is augmented by any factor $ c \ge 1 $ c ≥ 1 , unless P = NP. We also show that the approximation ratio is unbounded for a reasonable class of algorithms for this problem. We then present k-Sequence, an algorithm that repeatedly serves the fastest set of k remaining requests. We show that k-Sequence has approximation ratio at most $ 2+\lceil \lambda \rceil /k $ 2 + ⌈ λ ⌉ / k and at least $ 1 + \lambda /k $ 1 + λ / k , where λ denotes the aspect ratio of the graph, and that the ratio $ 1 + \lambda /k $ 1 + λ / k is tight when $ 1 + \lambda /k \ge k $ 1 + λ / k ≥ k. We also show that even as k grows beyond the size of λ, the ratio never improves below 9/7. [ABSTRACT FROM AUTHOR]

This research aims to study the estimation of parameters for a Burr‐XII distribution and to investigate optimal sampling plans under progressive Type‐I censoring (PTIC). For point estimation, we employed the maximum‐likelihood estimation (MLE) method using two numerical approaches: Newton–Raphson and the Expectation–Maximization algorithm. We also utilized Bayesian estimation with squared error loss and linear exponential loss functions. Specifically, two approximate Bayesian methods, the Lindley and Tierney‐Kadane methods were examined. Additionally, Bayesian numerical estimation was performed using Markov Chain Monte Carlo with the Metropolis‐Hastings (MH) algorithm. For interval estimation, we constructed asymptotic confidence intervals for MLE and the highest posterior density method within the Bayesian framework. The practical study involved Monte Carlo simulations to assess the efficiency and accuracy of the proposed estimation methods across different PTIC schemes. A real data analysis is also provided to illustrate the practical application of these methodologies in analyzing a clinical trial dataset. Data from a clinical trial using a PTIC scheme reveals patterns in pain relief, aiding in evaluating the antibiotic ointment's effectiveness. The study further investigates optimal sampling plans for the Burr‐XII distribution under PTIC. [ABSTRACT FROM AUTHOR]

It is currently an unsolved problem to determine whether, for every 2-list assignment L of a ▵ -free planar graph G, there exists an independent set A L such that G [ V G \ A L ] is L-colorable. However, in this paper, we take a slightly different approach to the above problem. We prove the N P -completeness of the decision problem of determining an independent set A such that G [ V G \ A ] is 2-choosable for ▵ -free, 4-colorable graphs of diameter 3. Building upon this notion, we examine the computational complexity of two optimization problems: minimum near-3-choosability and minimum 2-choosable-edge-deletion. In the former problem, the goal is to find an independent set A of minimum size in a given graph G, such that the induced subgraph G [ V G \ A ] is 2-choosable. We establish that this problem is N P -hard to approximate within a factor of | V G | 1 - ϵ for any ϵ > 0 , for planar bipartite graphs of arbitrary large girth. On the other hand, the problem of minimum 2-choosable-edge-deletion involves determining an edge set F ⊆ E G of minimum cardinality such that the spanning subgraph G [ E G \ F ] is 2-choosable. We prove that this problem can be approximated within a factor of O (log | V G |) . [ABSTRACT FROM AUTHOR]

We present a novel approach to performing fitness approximation in genetic algorithms (GAs) using machine learning (ML) models, focusing on dynamic adaptation to the evolutionary state. We compare different methods for (1) switching between actual and approximate fitness, (2) sampling the population, and (3) weighting the samples. Experimental findings demonstrate significant improvement in evolutionary runtimes, with fitness scores that are either identical or slightly lower than those of the fully run GA—depending on the ratio of approximate-to-actual-fitness computation. Although we focus on evolutionary agents in Gymnasium (game) simulators—where fitness computation is costly—our approach is generic and can be easily applied to many different domains. [ABSTRACT FROM AUTHOR]

High-dimensional meteorological data offer a comprehensive overview of meteorological conditions. Nevertheless, predicting regional high-dimensional meteorological data poses challenges due to the vast scale and rapid changes. Apart from slow conventional numerical weather prediction methods, recently developed deep learning methods often fail to fully integrate spatial information of the high-dimensional data and require a significant amount of computational resources. This paper presents the spatiotemporal analysis fitting prediction algorithm (SA-Fit), an approximation algorithm for regional high-dimensional meteorological data prediction. SA-Fit proposes two key designs to achieve efficient prediction of the high-dimensional data. SA-Fit introduces a lightweight Transformer-based spatiotemporal analysis network to encode spatiotemporal information, which can integrate the interaction information between different coordinates in the data. Furthermore, SA-Fit introduces explicit functions with a lasso penalty to fit variations in high-dimensional meteorological data, achieving the prediction of a large amount of data with minimal prediction values. We performed experiments using the ERA5 dataset from the Shanghai and Xi'an regions. The experimental results show that SA-Fit is comparable to other advanced deep learning prediction methods in overall prediction performance. SA-Fit shortens training time and significantly reduces model parameters while using the Transformer structure to ensure prediction accuracy. [ABSTRACT FROM AUTHOR]

We describe a simple deterministic O (ε - 1 log Δ) round distributed algorithm for (2 α + 1) (1 + ε) approximation of minimum weighted dominating set on graphs with arboricity at most α . Here Δ denotes the maximum degree. We also show a lower bound proving that this round complexity is nearly optimal even for the unweighted case, via a reduction from the celebrated KMW lower bound on distributed vertex cover approximation (Kuhn et al. in JACM 63:116, 2016). Our algorithm improves on all the previous results (that work only for unweighted graphs) including a randomized O (α 2) approximation in O (log n) rounds (Lenzen et al. in International symposium on distributed computing, Springer, 2010), a deterministic O (α log Δ) approximation in O (log Δ) rounds (Lenzen et al. in international symposium on distributed computing, Springer, 2010), a deterministic O (α) approximation in O (log 2 Δ) rounds (implicit in Bansal et al. in Inform Process Lett 122:21–24, 2017; Proceeding 17th symposium on discrete algorithms (SODA), 2006), and a randomized O (α) approximation in O (α log n) rounds (Morgan et al. in 35th International symposiumon distributed computing, 2021). We also provide a randomized O (α log Δ) round distributed algorithm that sharpens the approximation factor to α (1 + o (1)) . If each node is restricted to do polynomial-time computations, our approximation factor is tight in the first order as it is NP-hard to achieve α - 1 - ε approximation (Bansal et al. in Inform Process Lett 122:21-24, 2017). [ABSTRACT FROM AUTHOR]

We propose a model to address the overlooked problem of node clustering in simple hypergraphs. Simple hypergraphs are suitable when a node may not appear multiple times in the same hyperedge, such as in co‐authorship datasets. Our model generalizes the stochastic blockmodel for graphs and assumes the existence of latent node groups and hyperedges are conditionally independent given these groups. We first establish the generic identifiability of the model parameters. We then develop a variational approximation Expectation‐Maximization algorithm for parameter inference and node clustering, and derive a statistical criterion for model selection. To illustrate the performance of our R package HyperSBM, we compare it with other node clustering methods using synthetic data generated from the model, as well as from a line clustering experiment and a co‐authorship dataset. [ABSTRACT FROM AUTHOR]

The Kemeny method is one of the popular tools for rank aggregation. However, computing an optimal Kemeny ranking is NP -hard. Consequently, the computational task of finding a Kemeny ranking has been studied under the lens of parameterized complexity with respect to many parameters. We study the parameterized complexity of the problem of computing all distinct Kemeny rankings. We consider the target Kemeny score, number of candidates, average distance of input rankings, maximum range of any candidate, and unanimity width as our parameters. For all these parameters, we already have FPT algorithms. We find that any desirable number of Kemeny rankings can also be found without substantial increase in running time. We also present FPT approximation algorithms for Kemeny rank aggregation with respect to these parameters. [ABSTRACT FROM AUTHOR]

Quantum Generative Adversarial Networks (QGANs) represent a useful development in quantum machine learning, using the particular properties of quantum mechanics to solve the challenges of data analysis and modeling. This paper brings up a general analysis of five QGAN architectures, focusing on their evolution, strengths, weaknesses, and limitations in noisy intermediate-scale quantum (NISQ) devices. Primary methods like Entangling Quantum GAN (EQ-GAN) and Quantum state fidelity (QuGAN) concentrate on stability, convergence, and robust performance on small-scale datasets such as 2 × 2 grayscale images. Intermediate models such as Image Quantum GAN (IQGAN) and Experimental Quantum GAN (EXQGAN) provide new ideas like trainable encoders and patch-based sub-generators that are scalable to 8 × 8 datasets with increasing noise resilience. The most advanced method is Parameterized Quantum Wasserstein GAN (PQWGAN), which uses a hybrid quantum-classical structure to obtain high-resolution image processing for 28 × 28 grayscale datasets while trying to maintain parameter efficiency. This study explores, analyzes, and summarizes critical problems of QGANs, including accuracy, convergence, parameter efficiency, image quality, performance metrics, and training stability under noisy conditions. In addition, developing QGANs can generate and train parameters in quantum approximation optimization algorithms. One of the useful applications of QGAN is generating medical datasets that can generate medical images from limited datasets to train specific medical models for the recognition of diseases. [ABSTRACT FROM AUTHOR]

This research work introduces a connection of adjoint Bernoulli's polynomials and a gamma function as a sequence of linear positive operators. Further, the convergence properties of these sequences of operators are investigated in various functional spaces with the aid of the Korovkin theorem, Voronovskaja-type theorem, first order of modulus of continuity, second order of modulus of continuity, Peetre's K-functional, Lipschitz condition, etc. In the last section, we extend our research to a bivariate case of these sequences of operators, and their uniform rate of approximation and order of approximation are investigated in different functional spaces. Moreover, we construct a numerical example to demonstrate the applicability of our results. [ABSTRACT FROM AUTHOR]

This research work focuses on λ -Szász–Mirakjan operators coupling generalized beta function. The kernel functions used in λ -Szász operators often possess even or odd symmetry. This symmetry influences the behavior of the operator in terms of approximation and convergence properties. The convergence properties, such as uniform convergence and pointwise convergence, are studied in view of the Korovkin theorem, the modulus of continuity, and Peetre's K-functional of these sequences of positive linear operators in depth. Further, we extend our research work for the bivariate case of these sequences of operators. Their uniform rate of approximation and order of approximation are investigated in Lebesgue measurable spaces of function. The graphical representation and numerical error analysis in terms of the convergence behavior of these operators are studied. [ABSTRACT FROM AUTHOR]

This paper presents an ultra-low power comparator with minimum delay and low offset, used in successive approximation register analog-to-digital converters (SAR ADCs) for biomedical system-on-chips (SoCs). To reduce the power consumption, the proposed comparator is designed with a minimum supply voltage in the sub-threshold region. Additionally, intermediate switches are utilized in the design to serve two purposes: 1) breaking the connection between the latch and preamplifier parts during the pre-charge phase to reduce power consumption, 2) reducing the parasitic resistance of the discharge path during the evaluation phase to enhance effective transconductance of the latch ( g m e f f , l a t c h ). Furthermore, the proposed design incorporates, two transistors as auxiliary paths to increase the speed of discharging in the latching process. Overall, the proposed design aims to achieve a low power and high-performance comparator simulated at a frequency of 50 kHz using TSMC 65nm CMOS technology. The post-layout simulation results show that the proposed structure enjoyed from an ultra-low power consumption of 141.4 pW as well as excellent delay and offset with 357 ns and 3.32 mV values, respectively. The occupied area of the designed layout for the proposed comparator is 106.8 μm2 allowed us to embed it in multi-channel recording system on chips (SoCs). The Figure of Merit (FoM) of the proposed comparator is 0.000463 fVW/Hz. Moreover, the proposed comparator has been validated by using it in successive approximation conversion algorithm with a sampling frequency of 1 kS/s. [ABSTRACT FROM AUTHOR]

In this paper, we study the Minimum Cost Submodular Cover (ℳ ) problem over the ground set of size n , which aims at finding a subset with the minimal cost required so that the utility submodular function exceeds a given threshold. The problem has recently attracted a lot of attention due to its applications in various domains of operations research and artificial intelligence. However, the existing algorithms for this problem may not be easy to parallelize because of their costly adaptive complexity. However, the existing algorithms for this problem may not be effectively parallelized because of their costly adaptive complexity. This paper proposes an efficient parallel algorithm that returns a (1 − λ , (1 +) (1 + log 1 λ)) -bicriteria approximation solution within O (log n) adaptive complexity, where λ , are fixed parameters. Our algorithm requires O (n 2 log 2 n) query complexity, however, it can reduce to O (n log 3 n) instead while retaining a low adaptive complexity of O (log 2 n). Therefore, our algorithm not only achieves the same approximation guarantees as the state of the art but also significantly improves the best-known low adaptive complexity algorithm for the above problem. [ABSTRACT FROM AUTHOR]

The k-path partition problem (kPP), defined on a graph G = (V , E) , is a well-known NP-hard problem when k ≥ 3 . The goal of the kPP is to find a minimum collection of vertex-disjoint paths to cover all the vertices in G such that the number of vertices on each path is no more than k. In this paper, we give two approximation algorithms for the kPP. The first one, called Algorithm 1, uses an algorithm for the (0,1)-weighted maximum traveling salesman problem as a subroutine. When G is undirected, the approximation ratio of Algorithm 1 is k + 12 7 - 6 7 k , which improves on the previous best-known approximation algorithm for every k ≥ 7 . When G is directed, Algorithm 1 is a k + 6 4 - 3 4 k -approximation algorithm, which improves the existing best available approximation algorithm for every k ≥ 10 . Our second algorithm, i.e. Algorithm 2, is a local search algorithm tailored for the kPP in undirected graphs with small k. Algorithm 2 improves on the approximation ratios of the best available algorithm for every k = 4 , 5 , 6 . Combined with Algorithms 1 and 2, we have improved the approximation ratio for the kPP in undirected graphs for each k ≥ 4 as well as the approximation ratio for the kPP in directed graphs for each k ≥ 10 . As for the negative side, we show that for any ϵ > 0 it is NP-hard to approximate the kPP (with k being part of the input) within the ratio O (k 1 - ϵ) , which implies that Algorithm 1 is asymptotically optimal. [ABSTRACT FROM AUTHOR]

In this paper, we address the vertex-traversing-constrained mixed Chinese postman problem (the VtcMCP problem), which is a further generalization of the Chinese postman problem, and this new problem has many practical applications in real life. Specifically, given a connected mixed graph G = (V , E ∪ A ; w , b) with length function w (·) on edges and arcs and traversal function b (·) on vertices, we are asked to determine a tour traversing each link (i.e., either edge or arc) at least once and each vertex v at most b(v) times, the objective is to minimize the total length of such a tour, where n = | V | is the number of vertices and m = | E ∪ A | is the number of links of G, respectively. We obtain the following four main results. (1) Given any two constants β ≥ 1 and α ≥ 1 , we prove that there is no polynomial-time algorithm with approximation ratios (1 , β) or (α , 1) for solving the VtcMCP problem, where an (h, k)-approximation algorithm for solving the VtcMCP problem is one algorithm that produces a solution with violating the vertex-traversing constraints by at most a ratio of h and with costing at most k times the optimal value; (2) We design a (3, 2)-approximation algorithm A to solve the VtcMCP problem in time O (m 2 log n) ; (3) We prove the fact that this algorithm A in (2) is indeed an exact algorithm to optimally solve the VtcMCP problem for the case E = ∅ ; (4) We present an exact algorithm to optimally solve the VtcMCP problem in time O (m 3) for the case A = ∅ . [ABSTRACT FROM AUTHOR]

Estimating consistently oriented normals for point clouds enables a number of important applications in computer graphics such as surface reconstruction. While local normal estimation is possible with simple techniques like principal component analysis (PCA), orienting these normals to be globally consistent has been a notoriously difficult problem. Some recent methods exploit various properties of the winding number formula to achieve global consistency with state-of-the-art performance. Despite their exciting progress, these algorithms either have high space/time complexity, or do not produce accurate and consistently oriented normals for imperfect data. In this paper, we propose a novel property from the winding number formula, termed Winding Number Normal Consistency (WNNC), to tackle this problem. The derived property is based on the simple observation that the normals (negative gradients) sampled from the winding number field should be codirectional to the normals used to compute the winding number field. Since the WNNC property itself does not resolve the inside/outside orientation ambiguity, we further propose to incorporate an objective function from Parametric Gauss Reconstruction (PGR). We propose to iteratively update normals by alternating between WNNC-based normal updates and PGR-based gradient descents, which leads to an embarrassingly simple yet effective iterative algorithm that allows fast and high-quality convergence to a globally consistent normal vector field. Furthermore, our proposed algorithm only involves repeatedly evaluating the winding number formula and its derivatives, which can be accelerated and parallelized using a treecode-based approximation algorithm due to their special structures. Exploiting this fact, we implement a GPU-accelerated treecode-based solver. Our GPU (and even CPU) implementation can be significantly faster than the recent state-of-the-art methods for normal orientation from raw points. Our code is integrated with the popular PyTorch framework to facilitate further research into winding numbers, and is publicly available at https://jsnln.github.io/wnnc/index.html. [ABSTRACT FROM AUTHOR]

Multiple signal classification (MUSIC) is a widely used direction of arrival (DoA)/angle of arrival (AoA) estimation algorithm applied to various application domains, such as autonomous driving, medical imaging, and astronomy. However, MUSIC is computationally expensive and challenging to implement in low-power hardware, requiring exploration of tradeoffs between accuracy, cost, and power. We present MUSIC-lite, which exploits approximate computing to generate a design space exploring accuracy-area-power tradeoffs. This is specifically applied to the computationally intensive singular value decomposition (SVD) component of the MUSIC algorithm in an orthogonal frequency-division multiplexing (OFDM) radar use case. MUSIC-lite incorporates approximate adders into the iterative CORDIC algorithm that is used for hardware implementation of MUSIC, generating interesting accuracy-area-power tradeoffs. Our experiments demonstrate MUSIC-lite’s ability to save an average of 17.25% on-chip area and 19.4% power with a minimal 0.14% error for efficient MUSIC implementations. [ABSTRACT FROM AUTHOR]