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]

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.

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]

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]

The convergence analysis for least-squares finite element methods led to various adaptive mesh-refinement strategies: Collective marking algorithms driven by the built-in a posteriori error estimator or an alternative explicit residual-based error estimator as well as a separate marking strategy based on the alternative error estimator and an optimal data approximation algorithm. This paper reviews and discusses available convergence results. In addition, all three strategies are investigated empirically for a set of benchmarks examples of second-order elliptic partial differential equations in two spatial dimensions. Particular interest is on the choice of the marking and refinement parameters and the approximation of the given data. The numerical experiments are reproducible using the author's software package octAFEM available on the platform Code Ocean. [ABSTRACT FROM AUTHOR]

The main aim of this study is the analysis of the impact that occupants' characteristics have on thermal comfort assessment, through establishing a novel PMVo model using an approximation method, based on the experimental data. The parameters which are chosen as model's inputs are the air temperature, mean radiant temperature, relative humidity, basic clothing insulation, air velocity and occupants characteristics – gender, age, height, and body mass, while the output is the PMVo, a novel thermal comfort index. Since existing standards concerning thermal comfort do not consider these occupants' characteristics, the main novelty of the introduced model is the inclusion of occupants' characteristics in the thermal comfort assessment. To ensure enhanced precision, the model is established using both linear regression and by training neural network. These two approximation methods are compared to determine which one is more applicable in the context of data approximation. Study shows that regardless of dataset based on which models are established and regardless of testing input values, neural network (R2 in the range of 99.87% to 99.96%) is a superior mathematical approximation algorithm compared to the linear regression (R2 in the range of 95.3% to 97.5%). Novel neural network based thermal comfort assessment model is used for investigation of occupants' characteristics impact on thermal comfort assessment. Analysis of the results showed that gender, age, height and body mass may significantly impact thermal comfort indices calculation, which implies the necessity of their inclusion in thermal comfort prediction and evaluation. Thus, the presented PMVo model may be highly beneficial to implement within existing thermal comfort standards, ensuring well-being and satisfaction with conditions of indoor environment for wider range of the occupants. [ABSTRACT FROM AUTHOR]

Given a graph G = (V , E) , the problem of Graph Burning is to find a sequence of nodes from V , called a burning sequence, to burn the whole graph. This is a discrete-step process, and at each step, an unburned vertex is selected as an agent to spread fire to its neighbors by marking it as a burnt node. A burnt node spreads the fire to its neighbors at the next consecutive step. The goal is to find the burning sequence of minimum length. The Graph Burning problem is NP-Hard for general graphs and even for binary trees. A few approximation results are known, including a 3 -approximation algorithm for general graphs and a 2 -approximation algorithm for trees. The Graph Burning on directed graphs is more challenging than on undirected graphs. In this paper, we propose (1) A 2. 7 5 -approximation algorithm for a cactus graph (undirected), (2) A 3 -approximation algorithm for multi-rooted directed trees (polytree) and (3) A 1. 9 0 5 -approximation algorithm for the single-rooted directed tree (arborescence). We implement all three approximation algorithms, and the results are shown for randomly generated cactus graphs, multi-rooted directed trees and single-rooted directed trees. [ABSTRACT FROM AUTHOR]

We study scheduling problems with release times and rejection costs with the objective function of minimizing the maximum lateness. Our main result is a PTAS for the single machine problem with an upper bound on the rejection costs. This result is extended to parallel, identical machines. The corresponding problem of minimizing the rejection costs with an upper bound on the lateness is also examined. We show how to compute a PTAS for determining an approximation of the Pareto frontier on both objective functions on parallel, identical machines. Moreover, we present an FPTAS with strongly polynomial time for the maximum lateness problem without release times on identical machines when the number of machines is constant. Finally, we extend this FPTAS to the case of unrelated machines. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a graph. For an edge e = x y ∈ E , the closed neighbourhood of e, denoted by N G [ e ] or N G [ x y ] , is the set N G [ x ] ∪ N G [ y ] . A vertex set L ⊆ V is liar’s vertex-edge dominating set of a graph G = (V , E) if for every e i ∈ E , | N G [ e i ] ∩ L | ≥ 2 and for every pair of distinct edges e i and e j , | (N G [ e i ] ∪ N G [ e j ]) ∩ L | ≥ 3 . This paper introduces the notion of liar’s vertex-edge domination which arises naturally from some applications in communication networks. Given a graph G, the Minimum Liar’s Vertex-Edge Domination Problem (MinLVEDP) asks to find a liar’s vertex-edge dominating set of G of minimum cardinality. In this paper, we study this problem from an algorithmic point of view. We show that MinLVEDP can be solved in linear time for trees, whereas the decision version of this problem is NP-complete for general graphs, chordal graphs, and bipartite graphs. We further study approximation algorithms for this problem. We propose two approximation algorithms for MinLVEDP in general graphs and p-claw free graphs. On the negative side, we show that the MinLVEDP cannot be approximated within 1 2 (1 8 - ϵ) ln | V | for any ϵ > 0 , unless N P ⊆ D T I M E (| V | O (log (log | V |)) . Finally, we prove that the MinLVEDP is APX-complete for bounded degree graphs and p-claw-free graphs for p ≥ 6 . [ABSTRACT FROM AUTHOR]

We present a new sorting algorithm, called adaptive ShiversSort, that exploits the existence of monotonic runs for sorting efficiently partially sorted data. This algorithm is a variant of the well-known algorithm TimSort, which is the sorting algorithm used in standard libraries of programming languages, such as Python or Java (for non-primitive types). More precisely, adaptive ShiversSort is a so-called \(k\) -aware merge-sort algorithm, a class that captures 'TimSort-like' algorithms and that was introduced by Buss and Knop. In this article, we prove that, although adaptive ShiversSort is simple to implement and differs only slightly from TimSort, its computational cost, in number of comparisons performed, is optimal within the class of natural merge-sort algorithms, up to a small additive linear term. This makes adaptive ShiversSort the first \(k\) -aware algorithm to benefit from this property, which is also a 33% improvement over TimSort's worst-case. This suggests that adaptive ShiversSort could be a strong contender for being used instead of TimSort. Then, we investigate the optimality of \(k\) -aware algorithms. We give lower and upper bounds on the best approximation factors of such algorithms, compared to optimal stable natural merge-sort algorithms. In particular, we design generalisations of adaptive ShiversSort whose computational costs are optimal up to arbitrarily small multiplicative factors. [ABSTRACT FROM AUTHOR]

The Fréchet distance is a popular measure of dissimilarity for polygonal curves. It is defined as a min–max formulation that considers all orientation-preserving bijective mappings between the two curves. Because of its susceptibility to noise, Driemel and Har-Peled introduced the shortcut Fréchet distance in 2012, where one is allowed to take shortcuts along one of the curves, similar to the edit distance for sequences. We analyse the parameterised version of this problem, where the number of shortcuts is bounded by a parameter \(k\). The corresponding decision problem can be stated as follows: Given two polygonal curves \(T\) and \(B\) of at most \(n\) vertices, a parameter \(k\) and a distance threshold \(\delta\) , is it possible to introduce \(k\) shortcuts along \(B\) such that the Fréchet distance of the resulting curve and the curve \(T\) is at most \(\delta\) ? We study this problem for polygonal curves in the plane. We provide a complexity analysis for this problem with the following results: (1) there exists a decision algorithm with running time in \(\mathcal{O}(kn^{2k+2}\log n)\) ; (2) assuming the exponential-time hypothesis (ETH), there exists no algorithm with running time bounded by \(n^{o(k)}\). In contrast, we also show that efficient approximate decider algorithms are possible, even when \(k\) is large. We present a \((3+\varepsilon)\) -approximate decider algorithm with running time in \(\mathcal{O}(kn^{2}\log^{2}n)\) for fixed \(\varepsilon\). In addition, we can show that, if \(k\) is a constant and the two curves are \(c\) -packed for some constant \(c\) , then the approximate decider algorithm runs in near-linear time. [ABSTRACT FROM AUTHOR]

In this paper, we address the trip-constrained vehicle routing cover problem (the TcVRC problem). Specifically, given a metric complete graph G = (V , E ; w) with a set D (⊆ V) of depots, a set J (= V \ D) of customer locations, each customer having unsplittable demand 1, and k vehicles with capacity Q, it is asked to find a set C = { C i | i = 1 , 2 , … , k } of k tours for k vehicles to service all customers, each tour for a vehicle starts and ends at one depot in D and permits to be replenished at some other depots in D before continuously servicing at most Q customers, i.e., the number of customers continuously serviced in per trip of each tour is at most Q (except the two end-vertices of that trip), where each trip is a path or cycle, starting at a depot and ending at other depot (maybe the same depot) in D, such that there are no other depots in the interior of that path or cycle, the objective is to minimize the maximum weight of such k tours in C , i.e., min C max { w (C i) | i = 1 , 2 , … , k } , where w (C i) is the total weight of edges in that tour C i . Considering k vehicles whether to have common depot or suppliers, we consider three variations of the TcVRC problem, i.e., (1) the trip-constrained vehicle routing cover problem with multiple suppliers (the TcVRC-MS problem) is asked to find a set C = { C i | i = 1 , 2 , … , k } of k tours mentioned-above, the objective is to minimize the maximum weight of such k tours in C ; (2) the trip-constrained vehicle routing cover problem with common depot and multiple suppliers (the TcVRC-CDMS problem) is asked to find a set C = { C i | i = 1 , 2 , … , k } of k tours mentioned-above, where each tour starts and ends at same depot v in D, each vehicle having its suppliers at some depots in D (possibly including v), the objective is to minimize the maximum weight of such k tours in C ; (3) the trip-constrained k-traveling salesman problem with non-suppliers (the TckTS-NS problem, simply the TckTSP-NS) is asked to find a set C = { C i | i = 1 , 2 , … , k } of k tours mentioned-above, where each tour starts and ends at same depot v in D, each vehicle having non-suppliers, the objective is to minimize the maximum weight of such k tours in C . As for the main contributions, we design some approximation algorithms to solve these three aforementioned problems in polynomial time, whose approximation ratios achieve three constants 8 - 2 k , 7 2 - 1 k and 5, respectively. [ABSTRACT FROM AUTHOR]

Public transportation system is one of the most effective ways to conserve energy and reduce carbon emissions. However, the traditional public transportation system does not provide customized service and cannot guarantee the arrival time to destination. To address these issues, we formulate the minimum shared bus scheduling problem to minimize the number of shared buses such that all orders can be completed under constraints of deadlines and capacity of shared bus. We propose the approximation algorithms, S‐MBSA for the shared bus with strong endurance and E‐MBSA for the large‐scale order scenario, to solve the minimum shared bus scheduling problem. We further formulate the constrained maximum revenue shared bus scheduling problem to maximize the revenue under the limited number of shared buses, and propose an approximation algorithm, CMRBSA, to find the shared bus route schedules. Through the extensive simulations, we demonstrate the significant superiority of S‐MBSA and E‐MBSA in terms of number of shared buses. Furthermore, CMRBSA outperforms the benchmark algorithms significantly in terms of revenue. [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]

We improve the approximation ratio for Maximum Weight Series-Parallel Subgraph from 1 / 2 to 1 / 2 + 1 / 60. [ABSTRACT FROM AUTHOR]

In the network flow interdiction problem (NFI), an interdictor aims to remove arcs of total cost at most a given budget B from a network with given arc costs and capacities such that the value of a maximum flow from a source s to a sink t is minimized. We present a polynomial-time (B + 1) -approximation algorithm for NFI with unit arc costs, which is the first approximation algorithm for any variant of network flow interdiction whose approximation ratio only depends on the budget available to the interdictor, but not on the size of the network. [ABSTRACT FROM AUTHOR]

This study analyzes the conditional gradient method for constrained multiobjective optimization problems, also known as the Frank–Wolfe method. We assume that the objectives are continuously differentiable, and the constraint set is convex and compact. We employ an average-type nonmonotone line search, which takes the average of the recent objective function values. The asymptotic convergence properties without convexity assumptions on the objective functions are established. We prove that every limit point of the sequence of iterates that is obtained by the proposed method is a Pareto critical point. An iteration-complexity bound is provided regardless of the convexity assumption on the objective functions. The effectiveness of the suggested approach is demonstrated by applying it to several benchmark test problems. In addition, the efficiency of the proposed algorithm in generating approximations of the entire Pareto front is compared to the existing Hager–Zhang conjugate gradient method, the steepest descent method, the monotone conditional gradient method, and a nonmonotone conditional gradient method. In finding empirical comparison, we utilize two commonly used performance matrices—inverted generational distance and hypervolume indicators. [ABSTRACT FROM AUTHOR]

This paper proposes a novel generalized partial linear mixed models (GPLMMs) with the random effects distribution distributed as a multivariate skew-normal distribution for discrete longitudinal data over time. Under the Bayesian framework, we extended the Bayesian version of adaptive lasso (least absolute shrinkage and selection operator) for linear regression to the Bayesian adaptive lasso with the least squares approximation (LSA) method for generalized partial linear mixed models. A hybrid algorithm combining the Gibbs sampler and the Metropolis-Hastings algorithm in conjunction with the Bayesian adaptive lasso with LSA is used to simultaneously obtain the Bayesian estimates of unknown parameters, smoothing function and random effects, as well as select important covariates in GPLMMs. Several simulation studies and a real example are presented to illustrate the proposed methodologies. [ABSTRACT FROM AUTHOR]

Robotic manipulation and locomotion often entail nearly-simultaneous collisions—such as heel and toe strikes during a foot step—with outcomes that are extremely sensitive to the order in which impacts occur. Robotic simulators and state estimation commonly lack the fidelity and accuracy to predict this ordering, and instead pick one with a heuristic. This discrepancy degrades performance when model-based controllers and policies learned in simulation are placed on a real robot. We reconcile this issue with a set-valued rigid-body model which generates a broad set of outcomes to simultaneous frictional impacts with any impact ordering. We first extend Routh's impact model to multiple impacts by reformulating it as a differential inclusion (DI), and show that any solution will resolve all impacts in finite time. By considering time as a state, we embed this model into another DI which captures the continuous-time evolution of rigid-body dynamics, and guarantee existence of solutions. We finally cast simulation of simultaneous impacts as a linear complementarity problem (LCP), and develop an algorithm for tight approximation of the post-impact velocity set with probabilistic guarantees. We demonstrate our approach on several examples drawn from manipulation and legged locomotion, and compare the predictions to other models of rigid and compliant collisions. [ABSTRACT FROM AUTHOR]

Many real-world applications arising from social networks, personalized recommendations, and others, require extracting a relatively small but broadly representative portion of massive data sets. Such problems can often be formulated as maximizing a monotone set function with cardinality constraints. In this paper, we consider a streaming model where elements arrive quickly over time, and create an effective, and low-memory algorithm. First, we provide the first single-pass linear-time algorithm, which is a a deterministic algorithm, achieves an approximation ratio of [ γ 4 a (1 + γ + γ 2 + γ 3) − ] for any ≥ 0 with a query complexity of ⌈ n / a ⌉ + a and a memory complexity of O (a k log (k) log (1 /)) , where a is a positive integer and γ is the submodularity ratio. However, the algorithm may produce less-than-ideal results. Our next result is to describe a multi-streaming algorithm, which is the first deterministic algorithm to attain an approximation ratio of 1 − e − γ − with linear query complexity. [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]

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]

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]

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]

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]

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 λ $\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]

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]

Hiring the right person for the job is crucial for the success of any organization. In "Selection and Ordering Policies for Hiring Pipelines via Linear Programming," Epstein and Ma study several problems motivated by a firm that is carrying out a recruitment process. Restricted to a finite time budget, the firm must decide who will be interviewed out of a pool of applicants and who will receive offers among the interviewed applicants. They develop approximation algorithms with constant factor guarantees that approach optimality when the number of vacant positions grows large. The algorithms they develop are nonadaptive: they fix a subset of candidates and an order to conduct the interviews and the order remains unchanged, independent of the outcomes of other interviews. Thus, they establish bounds on the adaptivity gap: a worst-case measure of how poorly non-adaptive algorithms can perform with respect to their adaptive counterparts. Motivated by hiring pipelines, we study three selection and ordering problems in which applicants for a finite set of positions are interviewed or sent offers. There is a finite time budget for interviewing/sending offers, and every interview/offer is followed by a stochastic realization of discovering the applicant's quality or acceptance decision, leading to computationally challenging problems. In the first problem, we study sequential interviewing and show that a computationally tractable, nonadaptive policy that must make offers immediately after interviewing is near optimal, assuming offers are always accepted. We further show how to use this policy as a subroutine for obtaining a polynomial-time approximation scheme. In the second problem, we assume that applicants have already been interviewed but only accept offers with some probability; we develop a computationally tractable policy that makes offers for the different positions in parallel, which can be used even if positions are heterogeneous, and is near optimal relative to a policy that can make the same total number of offers one by one. In the third problem, we introduce a parsimonious model of overbooking where all offers are sent simultaneously, and a linear penalty is incurred for each acceptance beyond the number of positions; we provide nearly tight bounds on the performance of practically motivated value-ordered policies. All in all, our paper takes a unified approach to three different hiring problems based on linear programming. Our results in the first two problems generalize and improve the existing guarantees in the literature that were between 1/8 and 1/2 to new guarantees that are at least 1 − 1 / e ≈ 63.2 %. We also numerically compare three different settings of making offers to candidates (sequentially, in parallel, or simultaneously), providing insight into when a firm should favor each one. Supplemental Material: The online appendices are available at https://doi.org/10.1287/opre.2023.0061. [ABSTRACT FROM AUTHOR]

Near-Optimal Bayesian Online Assortment of Reusable Resources Motivated by rental services in e-commerce, we consider revenue maximization in the online assortment of reusable resources for different types of arriving consumers. We design competitive online algorithms compared with the optimal online policy in the Bayesian setting, where consumer types are drawn independently from known heterogeneous distributions over time. In scenarios with large initial inventories, our main result is a near-optimal competitive algorithm for reusable resources. Our algorithm relies on an expected linear programming (LP) benchmark, solves this LP, and simulates the solution through independent randomized rounding. The main challenge is achieving inventory feasibility efficiently using these simulation-based algorithms. To address this, we design discarding policies for each resource, balancing inventory feasibility and revenue loss. Discarding a unit of a resource impacts future consumption of other resources, so we introduce postprocessing assortment procedures to design and analyze our discarding policies. Additionally, we present an improved competitive algorithm for nonreusable resources and evaluate our algorithms using numerical simulations on synthetic data. Motivated by the applications of rental services in e-commerce, we consider revenue maximization in online assortment of reusable resources for a stream of arriving consumers with different types. We design competitive online algorithms with respect to the optimum online policy in the Bayesian setting in which types are drawn independently from known heterogeneous distributions over time. In the regime where the minimum of initial inventories c min is large, our main result is a near-optimal 1 − min (1 2 , log (c min) / c min ) competitive algorithm for the general case of reusable resources. Our algorithm relies on an expected LP benchmark for the problem, solves this LP, and simulates the solution through an independent randomized rounding. The main challenge is obtaining point-wise inventory feasibility in a computationally efficient fashion from these simulation-based algorithms. To this end, we use several technical ingredients to design discarding policies—one for each resource. These policies handle the trade-off between the inventory feasibility under reusability and the revenue loss of each of the resources. However, discarding a unit of a resource changes the future consumption of other resources. To handle this new challenge, we also introduce postprocessing assortment procedures that help with designing and analyzing our discarding policies as they run in parallel, which might be of independent interest. As a side result, by leveraging techniques from the literature on prophet inequality, we further show an improved near-optimal 1 − 1 / c min + 3 competitive algorithm for the special case of nonreusable resources. We finally evaluate the performance of our algorithms using the numerical simulations on the synthetic data. Funding: R. Niazadeh's research is partially supported by an Asness Junior Faculty Fellowship from the University of Chicago Booth School of Business. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2020.0687. [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]

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]

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]

In this work, we consider the properties of the two-term Machin-like formula and develop an algorithm for computing digits of π by using its rational approximation. In this approximation, both terms are constructed by using a representation of 1 / π in the binary form. This approach provides the squared convergence in computing digits of π without any trigonometric functions and surd numbers. The Mathematica codes showing some examples are presented. [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]

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]

With the progress in Global Navigation Satellite Systems (GNSS) technology, accurate geoid modelling has started to play an essential role in geodetic applications such as establishing height datum as a continuous surface model and related vertical control for infrastructure projects. Thus, numerous geoid modelling methods have been offered since 1990's, each of them has its own algorithm and approximation theories. Classical Stokes-Helmert is one of the most well-known methods all over the world by geodetic communities. However, a user-friendly software package of the method is not publicly accessible on the Internet. Therefore, a compact and user-friendly software package "CSHSOFT" is developed and presented for scholars in this field. A fractionated programming strategy has been treated to build individual components striving high accuracy and computational efficiency for geoid heights. Subsequently, the CSHSOFT is simply tested to construct a geoid model in the mountainous area in Auvergne test-bed where several geoid modelling techniques are implemented. Afterward, the new geoid model of the region is externally evaluated by GNSS-levelling data in terms of rigorous orthometric heights. The fitting statistics of 2.75 cm and 0.36 ppm in absolute and relative height differences fairly indicate that the CSHSOFT is a vigorous tool for gravimetric geoid modelling, and can be comfortably employed for geoscientific and technical studies. [ABSTRACT FROM AUTHOR]