Search

Computing optimal subset repairs and optimal update repairs of an inconsistent database has a wide range of applications and is becoming standalone research problems. However, these problems have not been well studied in terms of both inapproximability and approximation algorithms. In this paper, we prove a new tighter inapproximability bound for computing optimal subset repairs. We show that it is frequently NP-hard to approximate an optimal subset repair within a factor better than 143/136. We develop an algorithm for computing optimal subset repairs with an approximation ratio (2 - 1 / 2 σ - 1) , where σ is the number of functional dependencies. We improve it when the database contains a large amount of quasi-Turán clusters. We then extend our work for computing optimal update repairs. We show it is NP-hard to approximate an optimal update repair within a factor better than 143/136 for representative cases. We further develop an approximation algorithm for computing optimal update repairs with an approximation ratio mlc(Σ ) (2 - 1 / 2 σ - 1) , where mlc(Σ ) depends on the given functional dependencies. We conduct experiments on real data to examine the performance and the effectiveness of our proposed approximation algorithms [ABSTRACT FROM AUTHOR]

Collective graphical model (CGM) is a probabilistic model that provides a framework for analyzing aggregated count data. Maximum a posteriori (MAP) inference of unobserved variables under given observations is one of the essential operations in CGM. Because the MAP inference problem is known to be NP-hard in general, the current mainstream approach is to solve an alternative problem obtained by approximating the objective function and applying continuous relaxation. However, this approach has two significant drawbacks. First, the quality of the solution deteriorates when the values in the count data are negligible due to the inaccuracy of Stirling's approximation. Second, the application of continuous relaxation causes the violation of integrality constraints. This paper proposes novel algorithms for MAP inference in CGMs on path graphs to overcome these problems. Our method is based on the discrete difference of convex algorithm (DCA); DCA is a general framework to minimize the sum of a convex function and a concave function by repeatedly minimizing surrogate functions. Utilizing the particular structure of path graphs, we efficiently solve the surrogate function minimization by minimum convex cost flow algorithms. Furthermore, our approach also leads to a new method of solving another important task; MAP inference of the sample size in CGM on path graphs. Our method is naturally applicable to this task, allowing us to design very efficient algorithms. Experimental results on synthetic and real-world datasets show the effectiveness of the proposed algorithms. [ABSTRACT FROM AUTHOR]

Automatic engraving machines have several industrial applications, such as nameplates, identification codes, and bar code engraving. It can also be used for engraving messages or pictures on decorative items in homes. Additionally, the proposed algorithm can be extended for obtaining the paths for 3D printers. The engraving process happens when the designs, messages, or pictures are carved into any item. The cost of engraving can be optimized by minimizing the movements of the automatic engraving machine. The movements include engraving motions and air motions. This work proposes a fast algorithm for obtaining the engraving path that guarantees the air motions are at most 150% of the optimal. Optimum engraving paths are commonly obtained using exponential time algorithms. The proposed algorithm is a 3/2 approximation algorithm that obtains the engraving path in polynomial time. The experimental results indicate that the proposed algorithm computes an efficient engraving path in a short time. [ABSTRACT FROM AUTHOR]

Currently, few approaches are available for mixed-integer nonlinear robust optimization. Those that do exist typically either require restrictive assumptions on the problem structure or do not guarantee robust protection. In this work, we develop an algorithm for convex mixed-integer nonlinear robust optimization problems where a key feature is that the method does not rely on a specific structure of the inner worst-case (adversarial) problem and allows the latter to be non-convex. A major challenge of such a general nonlinear setting is ensuring robust protection, as this calls for a global solution of the non-convex adversarial problem. Our method is able to achieve this up to a tolerance, by requiring worst-case evaluations only up to a certain precision. For example, the necessary assumptions can be met by approximating a non-convex adversarial via piecewise relaxations and solving the resulting problem up to any requested error as a mixed-integer linear problem. In our approach, we model a robust optimization problem as a nonsmooth mixed-integer nonlinear problem and tackle it by an outer approximation method that requires only inexact function values and subgradients. To deal with the arising nonlinear subproblems, we render an adaptive bundle method applicable to this setting and extend it to generate cutting planes, which are valid up to a known precision. Relying on its convergence to approximate critical points, we prove, as a consequence, finite convergence of the outer approximation algorithm. As an application, we study the gas transport problem under uncertainties in demand and physical parameters on realistic instances and provide computational results demonstrating the efficiency of our method. [ABSTRACT FROM AUTHOR]

Tverberg's theorem states that for any k ≥ 2 and any set P ⊂ R d of at least (d + 1) (k - 1) + 1 points in d dimensions, we can partition P into k subsets whose convex hulls have a non-empty intersection. The associated search problem of finding the partition lies in the complexity class CLS = PPAD ∩ PLS , but no hardness results are known. In the colorful Tverberg theorem, the points in P have colors, and under certain conditions, P can be partitioned into colorful sets, in which each color appears exactly once and whose convex hulls intersect. To date, the complexity of the associated search problem is unresolved. Recently, Adiprasito, Bárány, and Mustafa (SODA 2019) gave a no-dimensional Tverberg theorem, in which the convex hulls may intersect in an approximate fashion. This relaxes the requirement on the cardinality of P. The argument is constructive, but does not result in a polynomial-time algorithm. We present a deterministic algorithm that finds for any n-point set P ⊂ R d and any k ∈ { 2 , ⋯ , n } in O (n d ⌈ log k ⌉) time a k-partition of P such that there is a ball of radius O ((k / n) diam (P)) that intersects the convex hull of each set. Given that this problem is not known to be solvable exactly in polynomial time, our result provides a remarkably efficient and simple new notion of approximation. Our main contribution is to generalize Sarkaria's method (Israel Journal Math., 1992) to reduce the Tverberg problem to the colorful Carathéodory problem (in the simplified tensor product interpretation of Bárány and Onn) and to apply it algorithmically. It turns out that this not only leads to an alternative algorithmic proof of a no-dimensional Tverberg theorem, but it also generalizes to other settings such as the colorful variant of the problem. [ABSTRACT FROM AUTHOR]

Multiobjective optimization approaches have allowed the improvement of technical features in industrial processes, focusing on more accurate approaches for solving complex engineering problems and support decision-making. This paper proposes a hybrid approach to optimize the 3D printing technology parameters, integrating the design of experiments and multiobjective optimization methods, as an alternative to classical parametrization design used in machining processes. Alongside the approach, a multiobjective differential evolution with uniform spherical pruning (usp-MODE) algorithm is proposed to serve as an optimization tool. The parametrization design problem considered in this research has the following three objectives: to minimize both surface roughness and dimensional accuracy while maximizing the mechanical resistance of the prototype. A benchmark with non-dominated sorting genetic algorithm II (NSGA-II) and with the classical sp-MODE is used to evaluate the performance of the proposed algorithm. With the increasing complexity of engineering problems and advances in 3D printing technology, this study demonstrates the applicability of the proposed hybrid approach, finding optimal combinations for the machining process among conflicting objectives regardless of the number of decision variables and goals involved. To measure the performance and to compare the results of metaheuristics used in this study, three Pareto comparison metrics have been utilized to evaluate both the convergence and diversity of the obtained Pareto approximations for each algorithm: hyper-volume (H), g-Indicator (G), and inverted generational distance. To all of them, ups-MODE outperformed, with significant figures, the results reached by NSGA-II and sp-MODE algorithms. [ABSTRACT FROM AUTHOR]

We consider robust discrete minimization problems where uncertainty is defined by a convex set in the objective. Assuming the existence of an integrality gap verifier with a bounded approximation guarantee for the LP relaxation of the non-robust version of the problem, we derive approximation algorithms for the robust version under different types of uncertainty, including polyhedral and ellipsoidal uncertainty. [ABSTRACT FROM AUTHOR]

We consider the k -Prize-Collecting Steiner Tree Problem. An instance is composed of an integer k and a graph G with costs on edges and penalties on vertices. The objective is to find a tree spanning at least k vertices which minimizes the cost of the edges in the tree plus the penalties of vertices not in the tree. This is one of the most fundamental network design problems and is a common generalization of the Prize-Collecting Steiner Tree Problem and the k -Minimum Spanning Tree Problem. Our main result is a 2-approximation algorithm, which improves on the currently best known approximation factor of 3.96 and has a faster running time. The algorithm builds on a modification of the primal-dual framework of Goemans and Williamson, and reveals interesting properties that can be applied to other similar problems. [ABSTRACT FROM AUTHOR]

We present a low-rank greedily adapted hp-finite element algorithm for computing an approximation to the solution of the Lyapunov operator equation. We show that there is a hidden regularity in eigenfunctions of the solution of the Lyapunov equation which can be utilized to justify the use of high order finite element spaces. Our numerical experiments indicate that we achieve eight figures of accuracy for computing the trace of the solution of the Lyapunov equation posed in a dumbbell-domain using a finite element space of dimension of only 10 4 degrees of freedom. Even more surprising is the observation that hp-refinement has an effect of reducing the rank of the approximation of the solution. [ABSTRACT FROM AUTHOR]

Existing methods of stress intensity factor (SIF) estimation are commonly based on the contact measurements of crack length with subsequent computation at taking into account the specimen geometry and loading process. The paper aims at the enhancement and verification of the non-contact and easily implemented technique for the assessment of mode I SIF during mechanical tests. Displacement fields constructed by digital image correlation (DIC) were approximated using Williams series in order to determine precise crack tip coordinates and proceed to the computation of stress intensity factor (SIF). The approximation algorithm was tested on linear-elastic and elastic–plastic ABAQUS models under various stress levels and the different Williams series term number. Besides numerical modeling of SIF, the algorithm was tested through assessment of crack propagation parameters under fatigue crack growth with the use of coarse- and fine-grained titanium samples. For the crack length range a/W ≤ 0.3, the approximation algorithm using the Williams series may be employed for estimating crack tip coordinates (crack length) and mode I stress intensity factor with satisfactory level of accuracy. The results of the study appeared to hold the promise of automated non-contact measurements of the crack length as well as stress intensity factor under fatigue crack propagation by employing DIC and appropriate high-performance real-time computing. [ABSTRACT FROM AUTHOR]

We consider a scheduling problem with m identical machines in parallel and the minimum makespan objective. The Longest Processing Time first (LPT) rule is a well-known approximation algorithm for this problem. Although its worst-case approximation ratio has been determined theoretically, it is known that the worst-case approximation ratio of LPT can be smaller with instances of smaller processing times. We assume that each job's processing time is not longer than 1/k times the optimal makespan for a given integer k. We derive the worst-case approximation ratio of the LPT algorithm in terms of parameters k and m. For that purpose, we divide the whole set of instances of the original problem into classes defined by different values of parameters k and m. On each of those classes, we derive an exact upper bound on the worst-case performance ratio as a function of parameters k and m. We also show that there exist classes of instances for which our worst-case approximation ratio is better than previous bounds. Our bound can complement previous research in terms of the performance analysis of LPT. [ABSTRACT FROM AUTHOR]

Given a graph G = (V , E) , the 3-path partition problem is to find a minimum collection of vertex-disjoint paths each of order at most 3 to cover all the vertices of V. The previous best approximation algorithm for the 3-path partition problem has a performance ratio 13/9, which is based on a simple local search strategy. We propose a more involved local search and show by an amortized analysis that it is a 4/3-approximation; we also design an instance to illustrate that the approximation ratio is tight. [ABSTRACT FROM AUTHOR]

In healthcare management, one important problem is how to efficiently allocate resources with limited capacities. From the point of view of a central decision maker with a long planning horizon, many healthcare resources such as appointment slots, operation rooms, and hospital beds can be regarded as reusable resources. Motivated by this observation, we study a new version of the assignment problem of reusable resources to sequentially arriving users. Different from previous works on reusable resources, we assume that each user will tell us the intended usage duration of each resource upfront before a decision needs to be made. In the setting where users arrive randomly according to a certain distribution, we propose an algorithm based on linear approximations of the optimal value functions, and show that it performs better than common methods developed for the case where usage times are known upon return in different simulations, as well as in a case study with real data. When users arrive in an adversarial order, we show by example that it is hard to design an algorithm with a lower-bounded competitive ratio. As users are much less likely to arrive in an adversarial order in reality, our proposed algorithm can be used to effectively schedule resources such as appointment slots and operation rooms in hospitals. [ABSTRACT FROM AUTHOR]

These bounds already improve previous results for HT ht and HT ht . In I Exponential-time quantum algorithms for graph coloring problems i , the authors present an exponential-space quantum algorithm computing the chromatic number of an I n i -vertex graph with running time HT ht using quantum random access memory (QRAM). The authors also present polynomial-space quantum algorithms with running time HT ht for the I k i -coloring problem, for HT ht , without using the QRAM, as well as HT ht -time classical algorithms that can be improved quadratically by Grover's search to obtain polynomial-space quantum algorithms. [Extracted from the article]

In crowd sensing systems, mobile users provide requesters with access to the resources of their mobile devices, such as the core processor, memory, and camera, to execute tasks in return for monetary payment. Existing works consider the offline setting where information about mobile users and requesters is publicly known. However, this assumption does not hold for crowd sensing systems in the real world, where mobile users and requesters can arrive and leave at any time. We address the problem of online task allocation and pricing in crowd sensing systems without making any assumptions about the future information of mobile users and requesters. We formulate this problem in an auction-based online setting and propose a feasible and online double auction mechanism. The proposed online mechanism considers one-to-many mapping, which permits multiple mobile devices to work together to complete the same task at different times in order to improve resource utilization. In addition, we show that the proposed mechanism maintains individual rationality, budget-balance, and computational tractability. Furthermore, we analyze the approximation ratio of the proposed approximation algorithm. The experimental results show that a user cannot increase her utility by untruthful declaration, and the proposed mechanism brings more economic benefit for the auctioneer and stimulates users to join the system. [ABSTRACT FROM AUTHOR]

This paper discusses an outer-approximation guided optimization method for constrained neural network inverse problems with rectified linear units. The constrained neural network inverse problems refer to an optimization problem to find the best set of input values of a given trained neural network in order to produce a predefined desired output in presence of constraints on input values. This paper analyzes the characteristics of optimal solutions of neural network inverse problems with rectified activation units and proposes an outer-approximation algorithm by exploiting their characteristics. The proposed outer-approximation guided optimization comprises primal and dual phases. The primal phase incorporates neighbor curvatures with neighbor outer-approximations to expedite the process. The dual phase identifies and utilizes the structure of local convex regions to improve the convergence to a local optimal solution. At last, computation experiments demonstrate the superiority of the proposed algorithm compared to a projected gradient method. [ABSTRACT FROM AUTHOR]

The network reconfiguration problem seeks to find a rooted tree T such that the energy of the (unique) feasible electrical flow over T is minimized. The tree requirement on the support of the flow is motivated by operational constraints in electricity distribution networks. The bulk of existing results on convex optimization over vertices of polytopes and on the structure of electrical flows do not easily give guarantees for this problem, while many heuristic methods have been developed in the power systems community as early as 1989. Our main contribution is to give the first provable approximation guarantees for the network reconfiguration problem. We provide novel lower bounds and corresponding approximation factors for various settings ranging from min { O (m - n) , O (n) } for general graphs, to O (n) over grids with uniform resistances on edges, and O (1) for grids with uniform edge resistances and demands. To obtain the result for general graphs, we propose a new method for (approximate) spectral graph sparsification, which may be of independent interest. Using insights from our theoretical results, we propose a general heuristic for the network reconfiguration problem that is orders of magnitude faster than existing methods in the literature, while obtaining comparable performance. [ABSTRACT FROM AUTHOR]

In this paper, we address the line-capacitated minimum Steiner tree problem (the Lc-MStT problem, for short), which is a variant of the (Euclidean) capacitated minimum Steiner tree problem and defined as follows. Given a set X = { r 1 , r 2 , ... , r n } of n terminals in R 2 , a demand function d : X → N and a positive integer C, we are asked to determine the location of a line l and a Steiner tree T l to interconnect these n terminals in X and at least one point located on this line l such that the total demand of terminals in each maximal subtree (of T l ) connected to the line l, where the terminals in such maximal subtree are all located at the same side of this line l, does not exceed the bound C. The objective is to minimize total weight ∑ e ∈ T l w (e) of such a Steiner tree T l among all line-capacitated Steiner trees mentioned-above, where weight w (e) = 0 if two endpoints of that edge e ∈ T l are located on the line l and otherwise weight w(e) is the Euclidean distance between two endpoints of that edge e ∈ T l . In addition, when this line l is as an input in R 2 and ∑ r ∈ X d (r) ≤ C holds, we refer to this version as the 1-line-fixed minimum Steiner tree problem (the 1Lf-MStT problem, for short). We obtain three main results. (1) Given a ρ st -approximation algorithm to solve the Euclidean minimum Steiner tree problem and a ρ 1 L f -approximation algorithm to solve the 1Lf-MStT problem, respectively, we design a (ρ st ρ 1 L f + 2) -approximation algorithm to solve the Lc-MStT problem. (2) Whenever demand of each terminal r ∈ X is less than C 2 , we provide a (ρ 1 L f + 2) -approximation algorithm to resolve the Lc-MStT problem. (3) Whenever demand of each terminal r ∈ X is at least C 2 , using the Edmonds' algorithm to solve the minimum weight perfect matching as a subroutine, we present an exact algorithm in polynomial time to resolve the Lc-MStT problem. [ABSTRACT FROM AUTHOR]

We introduce a variant of the Shortest Path Problem (SPP), in which we impose additional constraints on the acceleration over the arcs, and call it Bounded Acceleration SPP (BASP). This variant is inspired by an industrial application: a vehicle needs to travel from its current position to a target one in minimum-time, following pre-defined geometric paths connecting positions within a facility, while satisfying some speed and acceleration constraints depending on the vehicle position along the currently traveled path. We characterize the complexity of BASP, proving its NP-hardness. We also show that, under additional hypotheses on problem data, the problem admits a pseudo-polynomial time-complexity algorithm. Moreover, we present an approximation algorithm with polynomial time-complexity with respect to the data of the original problem and the inverse of the approximation factor ϵ . Finally, we present some computational experiments to evaluate the performance of the proposed approximation algorithm. [ABSTRACT FROM AUTHOR]

In this paper, motivated by many practical applications, we address the 1-line minimum rectilinear Steiner tree (1L-MRStT) problem, which is a variation of the Euclidean minimum rectilinear Steiner tree problem. More specifically, given n points in the Euclidean plane R 2 , it is asked to find the location of a line l and a Steiner tree T(l), consisting only of vertical and horizontal line segments plus several successive segments located on this line l, to interconnect these n points and at least one point located on the line l, the objective is to minimize total weight of this Steiner tree T(l), i.e., min { ∑ u v ∈ T (l) w (u , v) | T(l) is a Steiner tree mentioned-above } , where we define a weight w (u , v) = 0 if the two endpoints u and v of that edge u v ∈ T (l) is located on the line l and otherwise we define a weight w(u, v) as the rectilinear distance between the two endpoints u and v of that edge u v ∈ T (l) . Given a line l as an input in R 2 , we denote this problem as the 1-line-fixed minimum rectilinear Steiner tree (1LF-MRStT) problem; Furthermore, when the Steiner points of T(l) are all located on the fixed line l, we recall this problem as the 1-line-fixed-constrained minimum rectilinear Steiner tree (1LFC-MRStT) problem. We provide three following main contributions. (1) We design an algorithm A C to optimally solve the 1LFC-MRStT problem, where the algorithm A C runs in time O (n log n) ; (2) We prove that this algorithm A C is a 1.5-approximation algorithm to solve the 1LF-MRStT problem; (3) Combining the algorithm A C for many times and a key lemma proved by some techniques of computational geometry, we present a 1.5-approximation algorithm to solve the 1L-MRStT problem, where this algorithm runs in time O (n 3 log n) , and we finally provide another approximation algorithm to solve a special version of the 1L-MRStT problem, where that new algorithm runs in lower time O (n 2 log n) . [ABSTRACT FROM AUTHOR]

Stochastic combinatorial optimization problems are usually defined as planning problems, which involve purchasing and allocating resources in order to meet uncertain needs. For example, network designers need to make their best guess about the future needs of the network and purchase capabilities accordingly. Facing uncertain in the future, we either "wait and see" changes, or postpone decisions about resource allocation until the requirements or constraints become realized. Specifically, in the field of stochastic combinatorial optimization, some inputs of the problems are uncertain, but follow known probability distributions. Our goal is to find a strategy that minimizes the expected cost. In this paper, we consider the two-stage finite-scenario stochastic set cover problem and the single sink rent-or-buy problem by presenting primal-dual based approximation algorithms for these two problems with approximation ratio 2 η and 4.39, respectively, where η is the maximum frequency of the element of the ground set in the set cover problem. [ABSTRACT FROM AUTHOR]

Mobile edge computing (MEC) allows a mobile device to offload tasks to the nearby server for remote execution to enhance the performance of user equipment. A major challenge of MEC is to design an efficient algorithm for task allocation. In contrast to previous work on MEC, which mainly focuses on single-task allocation for a mobile device with only one task to be completed, this paper considers a mobile device with multiple tasks or an application with multiple tasks. This assumption does not hold in real settings because a mobile device may have multiple tasks waiting to execute. We address the problem of task allocation with minimum total energy consumption considering multi-task settings in MEC, in which a mobile device has one or more tasks. We consider the binary computation offloading mode and formulate multi-task allocation as an integer programming problem that is strongly NP-hard. We propose an approximation algorithm and show it is a polynomial-time approximation scheme that saves the maximum energy. Therefore, our proposed algorithm achieves a tradeoff between optimality loss and time complexity. We analyze the performance of the proposed algorithm by performing extensive experiments. The results of the experiments demonstrate that our proposed approximation algorithm is capable of finding near-optimal solutions, and achieves a good balance of speed and quality. [ABSTRACT FROM AUTHOR]

Smart manufacturing systems based on cloud computing deal with large amounts of data for various IoT devices, resulting in several challenges, including high latency and high bandwidth usage. Since fog computing physically close to IoT devices can alleviate these issues, much attention has recently been focused on this area. Fans are nearly ubiquitous in manufacturing sites for cooling and ventilation purposes. Thereby, we built a fan system with an accelerometer installed and monitored the operating state of the fan. We analyzed time-series data transmitted from the accelerometer. We applied machine learning under streaming data analytics at the fog computing level to create a fan's cyber-physical model (CPM). This work employed the symbolic approximation algorithm to approximate the time series data as symbols of arbitrary length. We compared the performance of CPMs made with five time-series classification (TSC) algorithms to monitor the state of the fan for anomalies in real time. The CPM made with the BOSS VS algorithm, a symbol approximation algorithm, accurately determined the current state of the fan within a fog computing environment, achieving approximately 98% accuracy at a 95% confidence level. Furthermore, we conducted a posthoc analysis, running statistical rigor tests on experimental data and simulation results. The workflow proposed in this work would be expected to be utilized for various IoT devices in smart manufacturing systems. [ABSTRACT FROM AUTHOR]

We study algorithms for the sliding-window model, an important variant of the data-stream model, in which the goal is to compute some function of a fixed-length suffix of the stream. We extend the smooth-histogram framework of Braverman and Ostrovsky (FOCS 2007) to almost-smooth functions, which includes all subadditive functions. Specifically, we show that if a subadditive function can be 1 + ε -approximated in the insertion-only streaming model, then it can be 2 + ε -approximated also in the sliding-window model with space complexity larger by factor O ε - 1 log w , where w is the window size. We demonstrate how our framework yields new approximation algorithms with relatively little effort for a variety of problems that do not admit the smooth-histogram technique. For example, in the frequency-vector model, a symmetric norm is subadditive and thus we obtain a sliding-window 2 + ε -approximation algorithm for it. Another example is for streaming matrices, where we derive a new sliding-window 2 + ε -approximation algorithm for Schatten 4-norm. We then consider graph streams and show that many graph problems are subadditive, including maximum submodular matching, minimum vertex-cover, and maximum k-cover, thereby deriving sliding-window O 1 -approximation algorithms for them almost for free (using known insertion-only algorithms). Finally, we design for every d ∈ 1 , 2 an artificial function, based on the maximum-matching size, whose almost-smoothness parameter is exactly d. [ABSTRACT FROM AUTHOR]

Consider the following Stochastic Score Classification problem. A doctor is assessing a patient's risk of developing a disease and can perform n different binary tests on the patient. The probability that test i is positive is p i and the outcomes of the n tests are independent. A patient's score is the total number of positive tests. Possible scores thus range between 0 and n. This range is divided into subranges, corresponding to risk classes (e.g., LOW, MEDIUM, or HIGH risk). Each test has an associated cost. To reduce testing cost, instead of performing all tests and determining an exact score, the doctor can perform tests sequentially and stop testing when it is possible to determine the patient's risk class. The problem is to determine the order in which the doctor should perform the tests, so as to minimize expected testing cost. We address the unit-cost case of the Stochastic Score Classification problem, and provide polynomial-time approximation algorithms for adaptive and non-adaptive versions of the problem. We also pose a number of open questions. [ABSTRACT FROM AUTHOR]

We present two types of simple algorithms for numerical approximations of the two-dimensional shallow water equations with variable topography by a dimensional splitting approach. The scheme of the first type has two steps and the the one of the second type has three steps of splitting dimensions in each iteration. In each step, the component computation incorporates a well-balanced method on Cartesian mesh in one-dimensional space. Tests show that these schemes provide us with a reasonable accuracy. Furthermore, we also establish the well-balanced property for both types of schemes. [ABSTRACT FROM AUTHOR]

The paper proposes an approach to the study of the standard optimal control problem based on the use of reduction to a finite-dimensional optimization problem with subsequent use of approximation of the main diagonal of the Hessian. The results of computational experiments on solving auxiliary optimization problems for separable, quasiseparable, and Rosenbrock–Skokov functions are presented. [ABSTRACT FROM AUTHOR]

Nowadays, users are becoming more reserved in uploading their own data to the servers of service providers for fear of personal information disclosure. In order to meet the need on privacy security, Federated Learning (FL) is proposed. As the nearest servers to users, edge servers are quite suitable for the execution of FL tasks, which results in a new concept called Federated Edge Learning (FEEL). It allows users to conduct model training locally without uploading their own data, thus avoiding privacy disclosure. However, the issue of Energy Consumption (EC) for training on devices becomes a main concern for users because the learning process is carried out on the devices with limited battery capacity. Then, from the standpoint of service providers, they pay more attention to the model performance (i.e., test dataset accuracy of the trained machine learning model) and usually have diverse requirements on it. Both EC and model performance are important metrics for FEEL, and from our engineering experience, service providers and users may have a conflict of interest in FEEL. In this paper, after modeling the two metrics, we identify the common factor (i.e., size of the training data) between them and are convinced that there is a tradeoff. Then, we add a workload constraint that regulates the common factor to the formulated problem and propose a resource optimization and device scheduling strategy to solve it, thus achieving the tradeoff between EC and model performance of FEEL. This strategy is based on the steepest descent method and approximation algorithm. The approximation ratio is also proved. By regulating the training workload threshold, the values of the two metrics can be dynamically adjusted. Achieving the tradeoff makes it possible to meet the needs of service providers and users at the same time. More specifically, it can minimize the energy consumption of training devices on the premise of meeting diverse requirements of service providers on model performance, which can not be realized by other FEEL frameworks that do not achieve the tradeoff. Simulation results show that our proposed strategy is able to achieve this tradeoff compared with two existing FEEL frameworks. Compared with another existing FEEL framework who also realizes the tradeoff, the tradeoff achieved by our proposed strategy is more biased towards EC. At the end of the simulation part, we summary the characteristics of the proposed and other three existing FEEL frameworks. [ABSTRACT FROM AUTHOR]

Illumination preprocessing is an important ingredient for handling lighting variation face recognition challenge. Nonetheless, existing methods are usually designed to be independent of the face recognition methods and the interaction between them is not yet well explored. In this paper, we formulate the face image illumination preprocessing and recognition into a unified sparse representation framework and propose a novel joint reflectance field estimation and sparse representation (JRSR) method for face recognition under extreme lighting conditions. The proposed method separates the identify factor and the interfered illumination of a query sample simultaneously by one nonconvex sparse optimizing model. We also present an efficient approximation algorithm to solve JRSR in this paper. Evaluation on several face databases and the experimental results of face recognition with illumination variation clearly demonstrate the advantages of our proposed JRSR algorithm in illumination preprocessing efficiency and recognition accuracy. [ABSTRACT FROM AUTHOR]

We study variants of the Strip Cover problem (SC) in which sensors with limited battery power are deployed on a line barrier, and the goal is to cover the barrier as long as possible. The energy consumption of a sensor depends on its sensing radius: Energy is drained in proportion to the sensor radius raised to a constant exponent α ≥ 1 . In the Set Once Strip Cover problem (OnceSC), the radius of each sensor can be set once, and the sensor can be activated at any time. SC k and O N C E SC k are variants of SC and OnceSC, respectively, in which each sensor is associated with a set of at most k predetermined radii. It was previously known that OnceSC is NP-hard when α = 1 , and the complexity of the case where α > 1 remained open. We extend the above-mentioned NP-hardness result in two ways: We show that OnceSC is NP-hard for every α > 1 and that OnceSC is strongly NP-hard for α = 1 . In addition, we show that O N C E SC k , for k ≥ 2 , is NP-hard, for any α ≥ 1 , even for uniform radii sets. On the positive side, we present (i) a 5 γ α -approximation algorithm for O N C E SC k , for k ≥ 1 , where γ is the maximum ratio between two radii associated with the same sensor; (ii) a 5-approximation algorithm for SC k , for every k ≥ 1 ; and (iii) a (5 + ε) -approximation algorithm for Strip Cover, for any constant ε > 0 . Finally, we present an O (n log n) -time algorithm for a variant of O N C E SC k in which all sensors must be activated at the same time. [ABSTRACT FROM AUTHOR]

Optimal energy delay scheduling for capacity allocation problems in interference channel energy harvesting wireless sensor networks (EH-WSN) address of static data streams as well as power surveying. The goal is to diminish the general regression of network. However, the optimization problem is not curved, which makes it difficult to obtain optimal solution. The major goal of this document is to directly address that original non-convex formulation with enhanced Beetle Antennae Search (BAS) algorithm competently gets optimal solution. The simulations in delay, delivery ratio, drop, energy, network life, overload, and throughput are performed; the predictable result shows the improved BAS algorithm performs better convex approximation system. This plan is helpful for other complex optimization problems in WSN. [ABSTRACT FROM AUTHOR]

In this paper, we address the problem of constructing required subgraphs using stock pieces of fixed length (CRS-SPFL, for short), which is a new variant of the minimum-cost edge-weighted subgraph (MCEWS, for short) problem. Concretely, for the MCEWS problem Q, it is asked to choose a minimum-cost subset of edges from a given graph G such that these edges can form a required subgraph G ′ . For the CRS-SPFL problem Q ′ , these edges in such a required subgraph G ′ are further asked to be constructed by plus using some stock pieces of fixed length L. The new objective, however, is to minimize the total cost to construct such a required subgraph G ′ , where the total cost is sum of the cost to purchase stock pieces of fixed length L and the cost to construct all edges in such a subgraph G ′ . We obtain the following three main results. (1) Given an α -approximation algorithm to solve the MCEWS problem, where α ≥ 1 (for the case α = 1 , the MCEWS problem Q is solved optimally by a polynomial-time exact algorithm), we design a 2 α -approximation algorithm and another asymptotic 7 α 4 -approximation algorithm to solve the CRS-SPFL problem Q ′ , respectively; (2) When Q is the minimum spanning tree problem, we provide a 3 2 -approximation algorithm and an AFPTAS to solve the problem Q ′ of constructing a spanning tree using stock pieces of fixed length L, respectively; (3) When Q is the single-source shortest paths tree problem, we present a 3 2 -approximation algorithm and an AFPTAS to solve the problem Q ′ of constructing a single-source shortest paths tree using stock pieces of fixed length L, respectively. [ABSTRACT FROM AUTHOR]

With the growing appetite for reducing carbon footprint, organizations are tirelessly working towards green practices and one such crucial practice is purchasing raw materials from sustainable suppliers (SSs). Inspired by the drift in purchase habits, several sustainable suppliers emerged in the market and a rational selection of a suitable sustainable supplier is a complex decision problem. There are many criteria associated with the evaluation of sustainable suppliers, and double hierarchy hesitant fuzzy linguistic (DHHFL) structure is a popular preference style that accepts complex linguistic expressions in the natural language form. Earlier studies on sustainable supplier selection infer that (i) complex linguistic expressions are not properly modeled, (ii) interrelationship among criteria must be considered during importance assessment, (iii) direct assignment of attitudinal values of experts causes bias and subjectivity, and (iv) nature of criteria play a crucial role in ranking SSs. To overcome these limitations, a novel MCMD framework is proposed in this study in which the attitudinal characteristic values of experts are calculated by using a variance approach. Besides, importance of diverse sustainable criteria is calculated by proposing novel attitude-CRITIC approach that supports proper capturing of interrelationship among criteria along with experts' attitude values. Later, weighted distance approximation algorithm is presented to DHHFL setting for personalized and cumulative ranking of SSs by properly considering nature of criteria. These methods are integrated to form a framework under DHHFL setting, and its usefulness is exemplified by using a case study of SS selection in an automotive firm. A comprehensive sensitivity analysis as well performed to test the validity of the proposed model approves the applicability, validity, and robustness of the model. Lastly, comparison is done with other methods to understand the merits and shortcomings of the proposal. [ABSTRACT FROM AUTHOR]

Consider an arc-capacitated network N through which an integer-valued flow must be sent from several source nodes to a sink node. Each feasible flow defines a corresponding multigraph with the same vertices as N and an edge for each arc of N , where the edge multiplicity is the flow in the respective arc. The maximum flow degree of a feasible flow is the maximum sum of the flow entering and leaving a node of N , i.e. the maximum degree of the corresponding multigraph. The minimum maximum flow degree problem (MMFDP) consists in determining on N a feasible flow such that its maximum flow degree is minimum. We present a polynomial time algorithm for this problem. We use its optimum value to derive an improved upper bound for the flow coloring problem (FCP), which consists in finding a feasible flow whose corresponding multigraph has the minimum chromatic index. Based on this procedure, we design an approximation algorithm for the FCP that improves the best known approximation factor. [ABSTRACT FROM AUTHOR]

We present two new algorithms for convex Mixed Integer Nonlinear Programming (MINLP), both based on the well known Extended Cutting Plane (ECP) algorithm proposed by Weterlund and Petersson. Our first algorithm, Refined Extended Cutting Plane (RECP), incorporates additional cuts to the MILP relaxation of the original problem, obtained by solving linear relaxations of NLP problems considered in the Outer Approximation algorithm. Our second algorithm, Linear Programming based Branch-and-Bound (LP-BB), applies the strategy of generating cuts that is used in RECP, to the linear approximation scheme used by the LP/NLP based Branch-and-Bound algorithm. Our computational results show that RECP and LP-BB are highly competitive with the most popular MINLP algorithms from the literature, while keeping the nice and desirable characteristic of ECP, of being a first-order method. [ABSTRACT FROM AUTHOR]

This study focuses on the perception of music performances when contextual factors, such as room acoustics and instrument, change. We propose to distinguish the concept of "performance" from the one of "interpretation", which expresses the "artistic intention". Towards assessing this distinction, we carried out an experimental evaluation where 91 subjects were invited to listen to various audio recordings created by resynthesizing MIDI data obtained through Automatic Music Transcription (AMT) systems and a sensorized acoustic piano. During the resynthesis, we simulated different contexts and asked listeners to evaluate how much the interpretation changes when the context changes. Results show that: (1) MIDI format alone is not able to completely grasp the artistic intention of a music performance; (2) usual objective evaluation measures based on MIDI data present low correlations with the average subjective evaluation. To bridge this gap, we propose a novel measure which is meaningfully correlated with the outcome of the tests. In addition, we investigate multimodal machine learning by providing a new score-informed AMT method and propose an approximation algorithm for the p-dispersion problem. [ABSTRACT FROM AUTHOR]

Gaussian processes (GPs) are popular models for functions, time series, and spatial fields, but direct application of GPs is computationally infeasible for large datasets. We propose a multi-scale Vecchia (MSV) approximation of GPs for modeling and analysis of multi-scale phenomena, which are ubiquitous in geophysical and other applications. In the MSV approach, increasingly large sets of variables capture increasingly small scales of spatial variation, to obtain an accurate approximation of the spatial dependence from very large to very fine scales. For a given set of observations, the MSV approach decomposes the data into different scales, which can be visualized to obtain insights into the underlying processes. We explore properties of the MSV approximation and propose an algorithm for automatic choice of the tuning parameters. We provide comparisons to existing approaches based on simulated data and using satellite measurements of land-surface temperature. [ABSTRACT FROM AUTHOR]

This work studies solution methods for approximating a given tensor by a sum of R rank-1 tensors with one or more of the latent factors being orthonormal. Such a problem arises from applications such as image processing, joint singular value decomposition, and independent component analysis. Most existing algorithms are of the iterative type, while algorithms of the approximation type are limited. By exploring the multilinearity and orthogonality of the problem, we introduce an approximation algorithm in this work. Depending on the computation of several key subproblems, the proposed approximation algorithm can be either deterministic or randomized. The approximation lower bound is established, both in the deterministic and the expected senses. The approximation ratio depends on the size of the tensor, the number of rank-1 terms, and is independent of the problem data. When reduced to the rank-1 approximation case, the approximation bound coincides with those in the literature. Moreover, the presented results fill a gap left in Yang (SIAM J Matrix Anal Appl 41:1797–1825, 2020), where the approximation bound of that approximation algorithm was established when there is only one orthonormal factor. Numerical studies show the usefulness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Edit distance is a measurement of similarity between two sequences such as strings, point sequences, or polygonal curves. Many matching problems from a variety of areas, such as signal analysis, bioinformatics, etc., need to be solved in a geometric space. Therefore, the geometric edit distance (GED) has been studied. In this paper, we describe the first strictly sublinear approximate near-linear time algorithm for computing the GED of two point sequences in constant dimensional Euclidean space. Specifically, we present a randomized O (n log 2 n) time O (n) -approximation algorithm. Then, we generalize our result to give a randomized α -approximation algorithm for any α ∈ [ log n , n / log n ] , running in time O (n 2 / α 2 log n) . Both algorithms are Monte Carlo and return approximately optimal solutions with high probability. [ABSTRACT FROM AUTHOR]

We introduce and study ℓ p -norm-multiway-cut: the input here is an undirected graph with non-negative edge weights along with k terminals and the goal is to find a partition of the vertex set into k parts each containing exactly one terminal so as to minimize the ℓ p -norm of the cut values of the parts. This is a unified generalization of min-sum multiway cut (when p = 1 ) and min–max multiway cut (when p = ∞ ), both of which are well-studied classic problems in the graph partitioning literature. We show that ℓ p -norm-multiway-cut is NP-hard for constant number of terminals and is NP-hard in planar graphs. On the algorithmic side, we design an O (log 1.5 n log 0.5 k) -approximation for all p ≥ 1 . We also show an integrality gap of Ω (k 1 - 1 / p) for a natural convex program and an O (k 1 - 1 / p - ϵ) -inapproximability for any constant ϵ > 0 assuming the small set expansion hypothesis. [ABSTRACT FROM AUTHOR]

We introduce and study a class of optimization problems we call replenishment problems with fixed turnover times: a very natural model that has received little attention in the literature. Clients with capacity for storing a certain commodity are located at various places; at each client the commodity depletes within a certain time, the turnover time, which is constant but can vary between locations. Clients should never run empty. The natural feature that makes this problem interesting is that we may schedule a replenishment (well) before a client becomes empty, but then the next replenishment will be due earlier also. This added workload needs to be balanced against the cost of routing vehicles to do the replenishments. In this paper, we focus on the aspect of minimizing routing costs. However, the framework of recurring tasks, in which the next job of a task must be done within a fixed amount of time after the previous one is much more general and gives an adequate model for many practical situations. Note that our problem has an infinite time horizon. However, it can be fully characterized by a compact input, containing only the location of each client and a turnover time. This makes determining its computational complexity highly challenging and indeed it remains essentially unresolved. We study the problem for two objectives: min–avg minimizes the average tour cost and min–max minimizes the maximum tour cost over all days. For min–max we derive a logarithmic factor approximation for the problem on general metrics and a 6-approximation for the problem on trees, for which we have a proof of NP-hardness. For min–avg we present a logarithmic factor approximation on general metrics, a 2-approximation for trees, and a pseudopolynomial time algorithm for the line. Many intriguing problems remain open. [ABSTRACT FROM AUTHOR]

Resource Minimization Fire Containment (RMFC) is a natural model for optimal inhibition of harmful spreading phenomena on a graph. In the RMFC problem on trees, we are given an undirected tree G, and a vertex r where the fire starts at, called root. At each time step, the firefighters can protect up to B vertices of the graph while the fire spreads from burning vertices to all their neighbors that have not been protected so far. The task is to find the smallest B that allows for saving all the leaves of the tree. The problem is hard to approximate up to any factor better than 2 even on trees unless P = NP (King and MacGillivray in Discret Math 310(3):614–621, 2010). Chalermsook and Chuzhoy (In: Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, Texas, USA, 17–19 Jan 2010, SIAM, pp 1334–1349, 2010) presented a Linear Programming (LP) based O (log ∗ n) approximation for RMFC on trees that matches the integrality gap of the natural Linear Programming relaxation. This was recently improved by Adjiashvili et al. (ACM Trans Algorithms 15(2):20:1–20:33, 2019) to a 12-approximation through a combination of LP rounding along with several new techniques. In this paper we present an asymptotic QPTAS for RMFC on trees. More specifically, let ϵ > 0 , and I be an instance of RMFC where the optimum number of firefighters to save all the leaves is O P T (I) . We present an algorithm which uses at most ⌈ (1 + ϵ) O P T (I) ⌉ many firefighters at each time step and runs in time n O (log log n / ϵ) . This suggests that the existence of an asymptotic PTAS is plausible especially since the exponent is O (log log n) , not O (log n) . Our result combines a more refined height reduction lemma than the one in Adjiashvili et al. (2019) with LP rounding and dynamic programming to find the solution. We also apply our height reduction lemma to the algorithm provided in Adjiashvili et al. (2019) plus a more careful analysis to improve their 12-approximation and provide a polynomial time ( 5 + ϵ )-approximation. [ABSTRACT FROM AUTHOR]

We study the nonlinear newsvendor problem concerning goods of a non-discrete nature, and a class of stochastic dynamic programs with several application areas such as supply chain management and economics. The class is characterized by continuous state and action spaces, either convex or monotone cost functions that are accessed via value oracles, and affine transition functions. We establish that these problems cannot be approximated to any degree of either relative or additive error, regardless of the scheme used. To circumvent these hardness results, we generalize the concept of fully polynomial-time approximation scheme allowing arbitrarily small additive and multiplicative error at the same time, while requiring a polynomial running time in the input size and the error parameters. We develop approximation schemes of this type for the classes of problems mentioned above. In light of our hardness results, such approximation schemes are "best possible". A computational evaluation shows the promise of this approach. [ABSTRACT FROM AUTHOR]

In this paper, we bound the integrality gap and the approximation ratio for maximum plane multiflow problems and deduce bounds on the flow-multicut-gap. We consider instances where the union of the supply and demand graphs is planar and prove that there exists a multiflow of value at least half the capacity of a minimum multicut. We then show how to convert any multiflow into a half-integer flow of value at least half the original multiflow. Finally, we round any half-integer multiflow into an integer multiflow, losing at most half the value thus providing a 1/4-approximation algorithm and integrality gap for maximum integer multiflows in the plane. [ABSTRACT FROM AUTHOR]

Sparse tensor best rank-1 approximation (BR1Approx), which is a sparsity generalization of the dense tensor BR1Approx, and is a higher-order extension of the sparse matrix BR1Approx, is one of the most important problems in sparse tensor decomposition and related problems arising from statistics and machine learning. By exploiting the multilinearity as well as the sparsity structure of the problem, four polynomial-time approximation algorithms are proposed, which are easily implemented, of low computational complexity, and can serve as initial procedures for iterative algorithms. In addition, theoretically guaranteed approximation lower bounds are derived for all the algorithms. We provide numerical experiments on synthetic and real data to illustrate the efficiency and effectiveness of the proposed algorithms; in particular, serving as initialization procedures, the approximation algorithms can help in improving the solution quality of iterative algorithms while reducing the computational time. [ABSTRACT FROM AUTHOR]

In this paper, we consider the group prize-collecting Steiner tree problem with submodular penalties (GPCST-SP problem). In this problem, we are given an undirected connected graph G = (V , E) with a pre-specified root r and a partition V = { V 0 , V 1 , ... , V k } of V with r ∈ V 0 . Assume c : E → R + is an edge cost function and p : 2 V → R + is a submodular penalty function, where R + is the set of nonnegative real numbers. For a group V i ∈ V , we say it is spanned by a tree if the tree contains at least one vertex of that group. The goal of the GPCST-SP problem is to find an r-rooted tree that minimizes the costs of the edges in the tree plus the penalty cost of the subcollection S containing these groups not spanned by the tree. Our main result is a 2I-approximation algorithm for the problem, where I = max { | V i | ∣ i = 0 , 1 , 2 , ... , k } . [ABSTRACT FROM AUTHOR]

We denote by Leafy Spanning k -Forest the problem of, given a positive integer k and a graph G with at most k components, finding a spanning forest in G with at most k components and the maximum number of leaves. The case k = 1 is known to be NP-hard, and is well studied in the literature, with the best approximation algorithm having been proposed more than 20 years ago by Solis-Oba. The best approximation algorithm known for Leafy Spanning k -Forest is a 3-approximation based on an approach by Lu and Ravi for the k = 1 case. We extend the algorithm of Solis-Oba to achieve a 2-approximation for Leafy Spanning k -Forest. [ABSTRACT FROM AUTHOR]

A classical result by Myerson (Math. Oper. Res. 6(1), 58-73, 1981) gives a characterization of an optimal auction for any given distribution of valuations of the bidders. We consider the situation where the distribution is not explicitly given but can be observed in a sample of auction results from the same distribution. A seminal paper by Morgenstern and Roughgarden (Adv.Neural Inf. Process. Syst. 28, 2015) proposes to learn a near-optimal auction from the hypothesis class of t-level auctions. They prove a bound on the sample complexity, i.e., the function f(ε,δ)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$f(\varepsilon , \delta )$$\end{document} of required samples to guarantee a certain level of precision (1-ε)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$(1-\varepsilon )$$\end{document} with a probability of at least (1-δ)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$(1-\delta )$$\end{document}, for the general single-parameter case and a tighter bound for the very restricted matroid case. We show a new bound for the case of independence systems, that widely generalizes matroids and contains several important combinatorial optimization problems. This bound of O~H2n4ε3\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\tilde{O}\left( \nicefrac {H^2n^4}{\varepsilon ^3}\right) $$\end{document} falls neatly between those known for the general and the matroid case. The class of independence systems contains several well known NP-hard problems such as knapsack. Therefore, the allocation itself might in practice be limited to α\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\alpha $$\end{document}-approximate solutions. In a second result we show that an approximation algorithm can be used without compromising the sample complexity. Also, the precision is affected only mildly, resulting in a factor of α·(1-ε)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\alpha \cdot (1-\varepsilon )$$\end{document}. [ABSTRACT FROM AUTHOR]

We discuss sequential stub matching for directed graphs and show that this process can be used to sample simple digraphs with asymptotically equal probability. The process starts with an empty edge set and repeatedly adds edges to it with a certain state-dependent bias until the desired degree sequence is fulfilled, whilst avoiding placing a double edge or self-loop. We show that uniform sampling is achieved in the sparse regime when the maximum degree dmax\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$d_\text {max}$$\end{document} is asymptotically dominated by m1/4\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$m^{1/4}$$\end{document}, where m is the number of edges. The proof is based on deriving various combinatorial estimates related to the number of digraphs with a given degree sequence and controlling concentration of these estimates in large digraphs. This suggests that sequential stub matching can be viewed as a practical algorithm for almost uniform sampling of digraphs. We show that this algorithm can be implemented to feature a linear expected runtime O(m). [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.Graphical abstract: 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]