Search

We study the problem of obtaining lower bounds for polynomial calculus (PC) and polynomial calculus resolution (PCR) on proof degree, and hence by [Impagliazzo et al. '99] also on proof size. [Alekhnovich and Razborov'03] established that if the clause-variable incidence graph of a conjunctive normal form (CNF) formula F is a good enough expander, then proving that F is unsatisfiable requires high PC/PCR degree. We further develop their techniques to show that if one can "cluster" clauses and variables in a way that "respects the structure" of the formula in a certain sense, then it is sufficient that the incidence graph of this clustered version is an expander. We also show how a weaker structural condition is sufficient to obtain lower bounds on width for the resolution proof system, and give a unified treatment that highlights similarities and differences between resolution and polynomial calculus (PC) lower bounds. As a corollary of our main technical theorem, we prove that the functional pigeonhole principle (FPHP) formulas require high PC/PCR degree when restricted to constant-degree expander graphs. This answers an open question in [Razborov'02], and also implies that the standard CNF encoding of the FPHP formulas require exponential proof size in polynomial calculus resolution (PCR). Thus, while onto-FPHP formulas are easy for polynomial calculus, as shown in [Riis'93], both FPHP and onto-PHP formulas are hard even when restricted to bounded-degree expanders. [ABSTRACT FROM AUTHOR]

AbstractFisher information plays crucial roles in statistics, while the moment-generating function provides a fundamental specification of probability density functions appeared in a variety of fields. In terms of the moment-generating function, we present a general form of the lower bound on Fisher information associated with parametric statistical models. The bound is derived from Cauchy-Schwarz inequality. We discuss the consequences of employing different inequalities and compare our results with the previously derived moments-based lower bound. [ABSTRACT FROM AUTHOR]

Quantum entanglement plays a pivotal role in quantum information processing. Quantifying quantum entanglement is a challenging and essential research area within the field. This manuscript explores the relationships between bipartite entanglement concurrence, multipartite entanglement concurrence, and genuine multipartite entanglement (GME) concurrence. We derive lower bounds on GME concurrence from these relationships, demonstrating their superiority over existing results through rigorous proofs and numerical examples. Additionally, we investigate the connections between GME concurrence and other entanglement measures, such as tangle and global negativity, in multipartite quantum systems. [ABSTRACT FROM AUTHOR]

The paper considers the Cauchy problem with small initial values for semilinear wave equations with weighted nonlinear terms. Similar to Strauss exponent p0(n) which is the positive root of the quadratic equation 1 + 1 2 (n + 1) p − 1 2 (n − 1) p 2 = 0 , we get smaller critical exponents pm(n),pm*(n) and have global existence in time when p>pm(n) or p>pm*(n). In addition, for the blow-up case, the introduction of the spacial weight shows the optimality of new upper and lower bound. [ABSTRACT FROM AUTHOR]

We prove that the uniform radius of spatial analyticity σ(t)$$ \sigma (t) $$ of solution at time t$$ t $$ to the one‐dimensional fourth‐order nonlinear Schrödinger equation i∂tu−∂x4u=|u|2u$$ i{\partial}_tu-{\partial}_x^4u={\left|u\right|}^2u $$cannot decay faster than 1/t$$ 1/\sqrt{t} $$ for large t$$ t $$, given that the initial data are analytic with fixed radius σ0$$ {\sigma}_0 $$. The main ingredients in the proof are a modified Gevrey space, a method of approximate conservation law, and a Strichartz estimate for free wave associated with the equation. [ABSTRACT FROM AUTHOR]

Copyright of Iranian Journal of Mathematical Chemistry is the property of University of Kashan and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

This paper analyses forward‐looking estimates of the expected market return in Australian. By utilising option prices, we compute a lower bound for the capital gain and dividend components of the expected return. Over a 17‐year period, the average 1‐month expected return lower bound is found to be 8.6% per annum, compared with an average realised return of 10.9% per annum. Our option‐based estimates demonstrate significant predictive power beyond historical averages and enable direct measurement of the expected return term structure. This approach complements traditional measures of expected returns and offers valuable insights for practitioners, academics, and policymakers in Australia. [ABSTRACT FROM AUTHOR]

The current study investigates the ultimate bearing capacity of obliquely/eccentrically loaded shallow strip foundations resting on a geogrid-reinforced granular fill with limited thickness over a very soft to soft clay layer. To this end, the lower bound theorems of the finite element limit analysis (FELA) and second-order cone programming (SOCP) are effectively exploited to simulate the underlying clay deposit, geogrid layer, and granular fill along with the inclined/eccentric loading exerted on the overlying footing. The accuracy of the adopted formulations is rigorously examined through several comparisons with the results of a well-established analytical approach in the literature. A comprehensive parametric study is then conducted to properly examine the influences of the geosynthetic layer characteristics and soft clay properties on the overall bearing capacity and failure envelope of the strip footing subjected to wide ranges of inclined and eccentric loadings. The results show that placement of a geogrid-reinforced granular fill layer over the soft clayey soil significantly increases the bearing capacity of the shallow foundation. The ultimate tensile strength of the reinforcement layer and the cohesion of the underlying very soft to soft clay deposit are also observed to have considerable effects on the size of failure envelopes. [ABSTRACT FROM AUTHOR]

Let [ · ] be the floor function. In the present paper we prove that when 1 < c < 12 11 and θ > 1 is a fixed, then there exist infinitely many prime numbers of the form [ n c tan θ (log n) ] . [ABSTRACT FROM AUTHOR]

A subset S of vertices in a graph G is a secure dominating set of G if S is a dominating set of G and, for each vertex u ⁄ ∈ S , there is a vertex v ∈ S such that u v is an edge and (S ∖ { v }) ∪ { u } is also a dominating set of G. The secure domination number of G , denoted by γ s (G) , is the cardinality of a smallest secure dominating sets of G. In this paper, we prove that, for any outerplanar graph with n ≥ 4 vertices, γ s (G) ≥ (n + 4) / 5 and the bound is tight. [ABSTRACT FROM AUTHOR]

An s, t Hamiltonian path P for an m × n rectangular grid graph G is a Hamiltonian path from the top-left corner s to the bottom-right corner t. We define an operation “square-switch” on s, t Hamiltonian paths P affecting only those edges of P that lie in some small (2 units by 2 units) square subgrid of G . We prove that when applied to suitable locations, the result of the square-switch is another s, t Hamiltonian path. Then we use square-switch to achieve a reconfiguration result for a subfamily of s, t Hamiltonian paths we call simple paths, that has the minimum number of bends for each maximal internal subpath connecting any two vertices on the boundary of the grid graph. We give an algorithmic proof that the Hamiltonian path graph G whose vertices represent simple paths is connected when edges arise from the square-switch operation: our algorithm reconfigures any given initial simple path P to any given target simple path P ′ in O ( | P | ) time and O ( | P | ) space using at most 5 | P | / 4 square-switches, where | P | = m × n is the number of vertices in the grid graph G and hence in any Hamiltonian path P for G . Thus the diameter of the simple path graph G is at most 5mn/ 4 for the square-switch operation, which we show is asymptotically tight for this operation. [ABSTRACT FROM AUTHOR]

In 2021, Gutman proposed a topological index for graphs known as the Sombor index. In this paper, we obtain several upper and lower bounds of the Sombor index of uniform hypergraphs, including those of hypertrees. Furthermore, we present a Nordhaus-Gaddum type result for the Sombor index of uniform hypergraphs. [ABSTRACT FROM AUTHOR]

In this work, we investigate the online MapReduce processing problem on mm uniform parallel machines, aiming at minimizing the makespan. Each job consists of two sets of tasks, namely, the map tasks and the reduce tasks. A job’s map tasks can be arbitrarily split and processed on different machines simultaneously, while its reduce tasks can only be processed after all its map tasks have been completed. We assume that the reduce tasks are preemptive, but cannot be processed on different machines in parallel. We provide a new lower bound for this problem and present an online algorithm with a competitive ratio of 2−1m2-\frac{1}{m} (mm is the number of machines) when the speeds of the machines are 1.

Some unnecessary costs in the film and television industry can be reduced through effective scheduling, like production lines in manufacturing. Traditional job scheduling problems that focus solely on minimizing total tardiness often overlook related personnel costs. Therefore, we consider both total tardiness and duration costs together in the film and television industry. Additionally, since these scenes (or jobs) may have relationships with one another (e.g., actors appearing repeatedly), we have developed several mathematical properties based on set theory. We propose a branch-and-bound algorithm to generate the optimal schedules. The experimental results demonstrate significant reductions in both types of costs. [ABSTRACT FROM AUTHOR]

We introduce the abstract notion of a chain, which is a sequence of n points in the plane, ordered by xcoordinates, so that the edge between any two consecutive points is unavoidable as far as triangulations are concerned. A general theory of the structural properties of chains is developed, alongside a general understanding of their number of triangulations. We also describe an intriguing new and concrete configuration, which we call the Koch chain due to itssimilarities to the Koch curve. A specific construction based on Koch chains is then shown to have Ω(9.08n ) triangulations. This is a significant improvement over the previous and long-standing lower bound of Ω(8.65n ) for the maximum number of triangulations of planar point sets. [ABSTRACT FROM AUTHOR]

In 2021, Gutman proposed a topological index for graphs known as the Sombor index. In this paper, we obtain several upper and lower bounds of the Sombor index of uniform hypergraphs, including those of hypertrees. Furthermore, we present a Nordhaus-Gaddum type result for the Sombor index of uniform hypergraphs.

This paper studies the optimal time decay to the Oldroyd-B model in R d ( d ≥ 2 ). By appealing to a refined pure energy method, we prove the lower and upper bounds of decay estimates of the global solutions. In particular, the lower bound of decay estimates is established by fully exploiting the structure of this system and by introducing a new combined quantity. [ABSTRACT FROM AUTHOR]

In this paper, we study the lower and upper bounds for Stokes eigenvalues by finite element schemes. For the schemes studied here, roughly speaking, the loss of the local approximation property of the discrete velocity and pressure spaces may lead to different computed bounds of the eigenvalues. Formally theoretical analysis is constructed based on certain mathematical hypotheses, and numerical experiments are given to illustrate the validity of the theory. [ABSTRACT FROM AUTHOR]

Tightness remains the primary goal in all modern estimation bounds. For very weak signals, tightness is enabled by appropriately selecting the prior probability distribution and bound family. While current bounds in global navigation satellite systems (GNSSs) assess the performance of carrier frequency estimators under Gaussian or uniform assumptions, the circular nature of frequency is overlooked. Of all bounds in the Bayesian framework, the Weiss--Weinstein bound (WWB) stands out because it is free from regularity conditions or restrictions on the prior distribution. Therefore, the WWB is extended for the current frequency estimation problem. A divide-and-conquer type of hyperparameter tuning method is developed to mitigate issues of computational complexity for the WWB family while enhancing tightness. Synthetic results show that for a von Mises prior probability distribution, the WWB provides a bound up to 22.5% tighter than the Ziv--Zakaï bound when the signal-to-noise ratio varies between -3.5 dB and -20 dB, where the GNSS signal is deemed extremely weak. [ABSTRACT FROM AUTHOR]

For a graph G, we define a total k-labeling ϕ as a combination of an edge labeling ϕe : E(G) → {1, 2, . . ., ke} and a vertex labeling ϕv : V (G) → {0, 2, . . ., 2kv}, where k = max {ke, 2kv}. The total k-labeling ϕ is called a vertex irregular reflexive k-labeling of G if any pair of vertices u, u' have distinct vertex weights wtϕ(u) ≠ wtϕ(u'), where wtϕ(u) = ϕ(u) + Σuu'∈E(G) ϕ(uu' ) for any vertex u ∈ V (G). The smallest value of k for which such a labeling exists is called the reflexive vertex strength of G, denoted by rvs(G). In this paper, we present a new lower bound for the reflexive vertex strength of any graph. We investigate the exact values of the reflexive vertex strength of generalized friendship graphs, corona product of two paths, and corona product of a cycle with isolated vertices by referring to the lower bound. This study discovers some interesting open problems that are worth further exploration. [ABSTRACT FROM AUTHOR]

The identification of both closed frequent high average utility itemsets (CFHAUIs) and generators of frequent high average utility itemsets (GFHAUIs) has substantial significance because they play an essential and concise role in representing frequent high average utility itemsets (FHAUIs). These concise summaries offer a compact yet crucial overview that can be much smaller. In addition, they allow the generation of non-redundant high average utility association rules, a crucial factor for decision-makers to consider. However, difficulty arises from the complexity of discovering these representations, primarily because the average utility function does not satisfy both monotonic and anti-monotonic properties within each equivalence class, that is for itemsets sharing the same subset of transactions. To tackle this challenge, this paper proposes an innovative method for efficiently extracting CFHAUIs and GFHAUIs. This approach introduces novel bounds on the average utility, including a weak lower bound called wlbau and a lower bound named auvlb . Efficient pruning strategies are also designed with the aim of early elimination of non-closed and/or non-generator FHAUIs based on the wlbau and auvlb bounds, leading to quicker execution and lower memory consumption. Additionally, the paper introduces a novel algorithm, CG-FHAUI, designed to concurrently discover both GFHAUIs and CFHAUIs. Empirical results highlight the superior performance of the proposed algorithm in terms of runtime, memory usage, and scalability when compared to a baseline algorithm. [ABSTRACT FROM AUTHOR]

A subset S of vertices in a graph G is a secure total dominating set of G if S is a total dominating set of G and, for each vertex u ⁄ ∈ S , there is a vertex v ∈ S such that u v is an edge and (S ∖ { v }) ∪ { u } is also a total dominating set of G. We show that if G is a maximal outerplanar graph of order n , then G has a total secure dominating set of size at most ⌊ 2 n / 3 ⌋. Moreover, if an outerplanar graph G of order n , then each secure total dominating set has at least ⌈ (n + 2) / 3 ⌉ vertices. We show that these bounds are best possible. [ABSTRACT FROM AUTHOR]

In the semialgebraic range searching problem, we are given a set of n points in ℝd, and we want to preprocess the points such that for any query range belonging to a family of constant complexity semialgebraic sets (Tarski cells), all the points intersecting the range can be reported or counted efficiently. When the ranges are composed of simplices, the problem is well-understood: It can be solved using S(n) space and with Q(n) query time with S(n)Q(n)d=Õ(nd), where the Õ(⋅) notation hides polylogarithmic factors and this trade-off is tight (up to no(1) factors). In particular, there exist “low space” structures that use O(n) space with O(n1-1/d) query time [8, 25] and “fast query” structures that use O(nd) space with O(log n) query time [9]. However, for general semialgebraic ranges, only “low space” solutions are known, but the best solutions [7] match the same trade-off curve as simplex queries, with O(n) space and Õ(n1−1/d) query time. It has been conjectured that the same could be done for the “fast query” case, but this open problem has stayed unresolved. Here, we disprove this conjecture. We give the first nontrivial lower bounds for semialgebraic range searching and other related problems. More precisely, we show that any data structure for reporting the points between two concentric circles, a problem that we call 2D annulus reporting, with Q(n) query time must use S(n)=...(n³/Q(n)5) space, where the ...(⋅) notation hides no(1) factors, meaning, for Q(n)=logO(1)n, ...(n³) space must be used. In addition, we study the problem of reporting the subset of input points in a polynomial slab defined by {(x,y)∈R²:P(x)≤y≤P(x)+w}, where P(x)=∑i=0Δaixi is a univariate polynomial of degree Δ and a0,…,aΔ,w are given at the query time, a problem that we call polynomial slab reporting. For this, we show a space lower bound of ...(nΔ+1/Q(n)(Δ+3)Δ/2), which implies that for Q(n)=logO(1)n, we must use ...(nΔ+1) space. We also consider the dual semialgebraic stabbing problems of semialgebraic range searching and present lower bounds for them. In particular, we show that in linear space, any data structure that solves 2D annulus stabbing problems must use ...(n2/3) query time. Note that this almost matches the upper bound obtained by lifting 2D annuli to 3D. Like semialgebraic range searching, we also present lower bounds for general polynomial slab stabbing problems. Again, our lower bounds are almost tight for linear size data structures in this case. [ABSTRACT FROM AUTHOR]

The rainbow connection concept was developed to determine the minimum number of passwords required to exchange encrypted information between two agents. If the information exchange involves divisions managing more than two agents, the rainbow connection concept can be extended to a hypergraph. In 2014, Carpentier et al. expanded the rainbow connection concept of graphs to hypergraphs. They implemented it on a minimally connected hypergraph, an $ r $-uniform complete hypergraph, an $ r $-uniform cycle hypergraph, and an $ r $-uniform complete multipartite hypergraph. However, they did not determine the rainbow connection numbers of hypertrees. A hypergraph $ \mathcal{H} $ is called a hypertree if there exists a host tree $ T $ such that each edge of $ \mathcal{H} $ induces a subtree in $ T $. Therefore, in this article, we consider the rainbow connection numbers of some classes of $ s $-overlapping $ r $-uniform hypertrees with size $ t $. For $ r\geq 2 $, $ 1\leq s < r $, and $ t\geq 1 $, an $ s $-overlapping $ r $-uniform hypertree with size $ t $ is an $ r $-uniform connected hypertree, with $ s $ being the maximum cardinality of the vertex set obtained from the intersection of each pair of edges. We provide the best lower bound of the rainbow connection number of a connected hypergraph. Then, we determine the rainbow connection numbers of six classes of $ s $-overlapping $ r $-uniform hypertrees with size $ t $.

We study property testing of properties that are definable in first-order logic (FO) in the bounded-degree graph and relational structure models. We show that any FO property that is defined by a formula with quantifier prefix ∃∗∀∗ is testable (i.e., testable with constant query complexity), while there exists an FO property that is expressible by a formula with quantifier prefix ∀∗∃∗ that is not testable. In the dense graph model, a similar picture is long known (Alon, Fischer, Krivelevich, Szegedy, Combinatorica 2000), despite the very different nature of the two models. In particular, we obtain our lower bound by an FO formula that defines a class of bounded-degree expanders, based on zig-zag products of graphs. We expect this to be of independent interest. We then use our class of FO definable bounded-degree expanders to answer a long-standing open problem for proximity-oblivious testers (POTs). POTs are a class of particularly simple testing algorithms, where a basic test is performed a number of times that may depend on the proximity parameter, but the basic test itself is independent of the proximity parameter. In their seminal work, Goldreich and Ron [STOC 2009; SICOMP 2011] show that the graph properties that are constant-query proximity-oblivious testable in the bounded-degree model are precisely the properties that can be expressed as a generalised subgraph freeness (GSF) property that satisfies the non-propagation condition. It is left open whether the non-propagation condition is necessary. We give a negative answer by showing that our property is a GSF property which is propagating. Hence in particular, our property does not admit a POT. For this result we establish a new connection between FO properties and GSF-local properties via neighbourhood profiles. [ABSTRACT FROM AUTHOR]

Randomized quadratures for integrating functions in Sobolev spaces of order \alpha \ge 1, where the integrability condition is with respect to the Gaussian measure, are considered. In this function space, the optimal rate for the worst-case root-mean-squared error (RMSE) is established. Here, optimality is for a general class of quadratures, in which adaptive non-linear algorithms with a possibly varying number of function evaluations are also allowed. The optimal rate is given by showing matching bounds. First, a lower bound on the worst-case RMSE of O(n^{-\alpha -1/2}) is proven, where n denotes an upper bound on the expected number of function evaluations. It turns out that a suitably randomized trapezoidal rule attains this rate, up to a logarithmic factor. A practical error estimator for this trapezoidal rule is also presented. Numerical results support our theory. [ABSTRACT FROM AUTHOR]

In this paper, we show that the radius of analyticity σ (t) of solutions to the one-dimensional nonlinear Schrödinger (NLS) equation i ∂ t u + ∂ x 2 u = | u | p − 1 u is bounded from below by c | t | − 2 3 when p > 3 and by c | t | − 4 5 when p = 3 as | t | → + ∞ , given initial data that is analytic with fixed radius. This improves results obtained by Tesfahun [On the radius of spatial analyticity for cubic nonlinear Schrödinger equations, J. Differential Equations 263(11) (2017) 7496–7512] for p = 3 and Ahn et al. [On the radius of spatial analyticity for defocusing nonlinear Schrödinger equations, Discrete Contin. Dyn. Syst. 40(1) (2020) 423–439] for any odd integers p > 3 , where they obtained a decay rate σ (t) ≥ c | t | − 1 for larger t. The proof of our main theorems is based on a modified Gevrey space introduced in [T. T. Dufera, S. Mebrate and A. Tesfahun, On the persistence of spatial analyticity for the beam equation, J. Math. Anal. Appl. 509(2) (2022) 126001], the local smoothing effect, maximal function estimate of the Schrödinger propagator, a method of almost conservation law, Schrödinger admissibility and one-dimensional Sobolev embedding. [ABSTRACT FROM AUTHOR]

For a graph G, the third neighborhood degree index of G is defined as: where G(a) represents the sum of degrees of all neighboring vertices of vertex a. In this short paper, we establish a new lower bound on the third neighborhood degree index of trees and characterize the extremal trees achieving this bound. [ABSTRACT FROM AUTHOR]

Numerous operational constraints within both industry and service sectors mandate the concurrent scheduling of tasks. This need is particularly evident in the assembly of products within manufacturing processes. This paper concentrates on minimizing makespan in the two-stage assembly flow shop problem. Our contributions include the introduction of novel dominance rules, a proposal for a heuristic method, and the development of a branch and bound algorithm. Additionally, we conduct an empirical analysis of makespan distribution for small-size instances. Through extensive experimentation, our study demonstrates the efficiency of the introduced dominance rules and the strong performance of the developed branch and bound algorithm. [ABSTRACT FROM AUTHOR]

The rainbow connection concept was developed to determine the minimum number of passwords required to exchange encrypted information between two agents. If the information exchange involves divisions managing more than two agents, the rainbow connection concept can be extended to a hypergraph. In 2014, Carpentier et al. expanded the rainbow connection concept of graphs to hypergraphs. They implemented it on a minimally connected hypergraph, an runiform complete hypergraph, an r-uniform cycle hypergraph, and an r-uniform complete multipartite hypergraph. However, they did not determine the rainbow connection numbers of hypertrees. A hypergraph H is called a hypertree if there exists a host tree T such that each edge of H induces a subtree in T. Therefore, in this article, we consider the rainbow connection numbers of some classes of s-overlapping r-uniform hypertrees with size t. For r ≥ 2, 1 ≤ s < r, and t ≥ 1, an s-overlapping r-uniform hypertree with size t is an r-uniform connected hypertree, with s being the maximum cardinality of the vertex set obtained from the intersection of each pair of edges. We provide the best lower bound of the rainbow connection number of a connected hypergraph. Then, we determine the rainbow connection numbers of six classes of s-overlapping r-uniform hypertrees with size t. [ABSTRACT FROM AUTHOR]

Given a large set U where each item a∈ U has weight w(a), we want to estimate the total weight \(W=\sum _{a∈ U} w(a)\) to within factor of 1± ɛ with some constant probability > 1/2. Since n=|U| is large, we want to do this without looking at the entire set U. In the traditional setting in which we are allowed to sample elements from U uniformly, sampling Ω (n) items is necessary to provide any non-trivial guarantee on the estimate. Therefore, we investigate this problem in different settings: in the proportional setting we can sample items with probabilities proportional to their weights, and in the hybrid setting we can sample both proportionally and uniformly. These settings have applications, for example, in sublinear-time algorithms and distribution testing. Sum estimation in the proportional and hybrid setting has been considered before by Motwani, Panigrahy, and Xu [ICALP, 2007]. In their article, they give both upper and lower bounds in terms of n. Their bounds are near-matching in terms of n, but not in terms of ɛ. In this article, we improve both their upper and lower bounds. Our bounds are matching up to constant factors in both settings, in terms of both n and ɛ. No lower bounds with dependency on ɛ were known previously. In the proportional setting, we improve their \(\tilde{O}(\sqrt {n}/ɛ ^{7/2})\) algorithm to \(O(\sqrt {n}/ɛ)\). In the hybrid setting, we improve \(\tilde{O}(\sqrt [3]{n}/ ɛ ^{9/2})\) to \(O(\sqrt [3]{n}/ɛ ^{4/3})\). Our algorithms are also significantly simpler and do not have large constant factors. We then investigate the previously unexplored scenario in which n is not known to the algorithm. In this case, we obtain a \(O(\sqrt {n}/ɛ + \log n / ɛ ^2)\) algorithm for the proportional setting, and a \(O(\sqrt {n}/ɛ)\) algorithm for the hybrid setting. This means that in the proportional setting, we may remove the need for advice without greatly increasing the complexity of the problem, while there is a major difference in the hybrid setting. We prove that this difference in the hybrid setting is necessary, by showing a matching lower bound. Our algorithms have applications in the area of sublinear-time graph algorithms. Consider a large graph G=(V, E) and the task of (1 ± ɛ)-approximating |E|. We consider the (standard) settings where we can sample uniformly from E or from both E and V. This relates to sum estimation as follows: we set U = V and the weights to be equal to the degrees. Uniform sampling then corresponds to sampling vertices uniformly. Proportional sampling can be simulated by taking a random edge and picking one of its endpoints at random. If we can only sample uniformly from E, then our results immediately give a \(O(\sqrt {|V|} / ɛ)\) algorithm. When we may sample both from E and V, our results imply an algorithm with complexity \(O(\sqrt [3]{|V|}/ɛ ^{4/3})\). Surprisingly, one of our subroutines provides an (1 ± ɛ)-approximation of |E| using \(\tilde{O}(d/ɛ ^2)\) expected samples, where d is the average degree, under the mild assumption that at least a constant fraction of vertices are non-isolated. This subroutine works in the setting where we can sample uniformly from both V and E. We find this remarkable since it is O(1/ɛ2) for sparse graphs. [ABSTRACT FROM AUTHOR]

Hansen (2005) obtained the efficiency bound (the lowest achievable risk) in the p-dimensional normal location model when p≥3, generalizing an earlier result of Magnus (2002) for the one-dimensional case (p = 1). The classes of estimators considered are, however, different in the two cases. We provide an alternative bound to Hansen's which is a more natural generalization of the one-dimensional case, and we compare the classes and the bounds. [ABSTRACT FROM AUTHOR]

In order to achieve time–frequency superresolution in comparison to the conventional Wigner distribution (WD), this study generalizes the well-known τ -Wigner distribution (τ -WD) with only one parameter τ to the multiple-parameter matrix-Wigner distribution (M-WD) with the parameter matrix M. According to operator theory, we construct Heisenberg's inequalities on the uncertainty product in M-WD domains and formulate two kinds of attainable lower bounds dependent on M. We solve the problem of lower bound minimization and obtain the optimality condition of M , under which the M-WD achieves superior time–frequency resolution. It turns out that the M-WD breaks through the limitation of the τ -WD and gives birth to some novel distributions other than the WD that could generate the highest time–frequency resolution. As an example, the two-dimensional linear frequency-modulated signal is carried out to demonstrate the time–frequency concentration superiority of the M-WD over the short-time Fourier transform and wavelet transform. [ABSTRACT FROM AUTHOR]

In this paper, we consider the Cumulative Capacitated Vehicle Routing Problem (CCVRP), which is used to model many real-world applications, especially in the area of supplying humanitarian aid after a natural disaster. Interestingly, in this study, Unmanned Aerial Vehicles (UAVs) so-called drones are used to assist the trucks in delivering parcels to customers. Each of them travels to different locations to perform specified tasks and meet periodically with the vehicle from which it takes off to swap its battery. In this paper, a mathematical model is formulated which is then tested with small-sized problems using CPLEX software. Due to the difficulty of solving large instances to optimality, we propose a heuristic algorithm based on a well-established type of cluster-first, route-second approach. Then, it is enhanced by some proposed properties. Hereafter, we develop a minimum spanning tree based-lower bound. Finally, extensive computational experiments are carried out by using instances from the literature. They show the good performance of the proposed heuristic algorithm to solve large instances in a very competitive running time. [ABSTRACT FROM AUTHOR]

We in this paper improve the well-known C. R. Johnson's lower bound for the smallest singular value via permutation matrices. A direct algorithm is also given to compute the new lower bound. [ABSTRACT FROM AUTHOR]

Supersaturated design is an important class of fractional factorial designs in which the number of experimental runs is not enough to estimate all the main effects. These designs are widely used in screening experiments, where the primary goal is to find important active factors at a low cost. The minimum β-aberration criterion is an appropriate criterion for measuring designs with quantitative factors. In this article, we first establish the explicit expression of β2 for three-level designs based on the relationship between the wordlength enumerator and the β-wordlength pattern. It can reduce the computational complexity of the β-wordlength pattern, and help provide an effective way for finding designs under the minimum β-aberration criterion. Moreover, a sharper lower bound of β2 is obtained, which can be considered as a benchmark for constructing optimal supersaturated designs. We further provide a simulated annealing algorithm to construct three-level supersaturated uniform designs with less β2. Finally, numerical results verify that our lower bound is sharper than the existing lower bound. [ABSTRACT FROM AUTHOR]

The partial sums of the series expansion of the Bessel function Jα of the first kind provide lower and upper bounds on the positive real axis for order α ≥-1=2. [ABSTRACT FROM AUTHOR]

In this paper, a tight lower bound for the differential entropy of the Gaussian mixture model is presented. First, the probability model of mixed Gaussian distribution that is created by mixing both discrete and continuous random variables is investigated in order to represent symmetric bimodal Gaussian distribution using the hyperbolic cosine function, on which a tighter upper bound is set. Then, this tight upper bound is used to derive a tight lower bound for the differential entropy of the Gaussian mixture model introduced. The proposed lower bound allows to maintain its tightness over the entire range of the model’s parameters and shows more tightness when compared with other bounds that lose their tightness over certain parameter ranges. The presented results are then extended to introduce a more general tight lower bound for asymmetric bimodal Gaussian distribution, in which the two modes have a symmetric mean but differ in terms of their weights. [ABSTRACT FROM AUTHOR]

Distributed key-value stores employ replication for high availability. Yet, they do not always efficiently take advantage of the availability of multiple replicas for each value and read operations often exhibit high tail latencies. Various replica selection strategies have been proposed to address this problem, together with local request scheduling policies. It is difficult, however, to determine what is the absolute performance gain each of these strategies can achieve. We present a formal framework allowing the systematic study of request scheduling strategies in key-value stores. We contribute a definition of the optimization problem related to reducing tail latency in a replicated key-value store as a minimization problem with respect to the maximum weighted flow criterion. By using scheduling theory, we show the difficulty of this problem and therefore the need to develop performance guarantees. We also study the behavior of heuristic methods using simulations that highlight which properties enable limiting tail latency: for instance, the EarliestFinishTime strategy—which uses the earliest next available time of servers—exhibits a tail latency that is less than half that of state-of-the-art strategies, often matching the lower bound. Our study also emphasizes the importance of metrics such as the stretch to properly evaluate replica selection and local execution policies. [ABSTRACT FROM AUTHOR]

We calculate an explicit lower bound on the proportion of elliptic curves that are modular over any Galois CM field not containing ζ 5 . Applied to imaginary quadratic fields, this proportion is at least 2 / 5. Applied to cyclotomic fields ℚ (ζ n) with 5 ∤ n , this proportion is at least 1 − ε with only finitely many exceptions of n , for any choice of ε > 0. [ABSTRACT FROM AUTHOR]

The pattern matching is one of the essential tasks in streaming time-series data mining. Its purpose is to identify all sliding windows in streaming time-series whose Euclidean Distances with predefined patterns are smaller than a threshold pre-determined. The pattern can be high-dimensional data and the streaming time-series is frequently updated. Thus, the brute-force method, which involves calculating Euclidean Distances between each sliding window and all patterns, is not effective in practical applications. This paper develops a lower bound-basedmethod that can perform pattern matching in less time while guaranteeing the same results as brute-force method. The proposed method achieves speedup without any sacrifice in matching accuracy. The block vector is utilized to calculate the lower bound of Euclidean Distance. Our proposal can safely eliminate many expensive Euclidean Distance calculations between patterns and sliding window; thus, the efficiency of pattern matching can be improved. Besides, we present an approach that can obtain the block vectors on-the-fly in the streaming scenarios to improve efficiency further. The experimental study in synthetic and real-life data sets verifies the efficiency and advantage of the proposals over the state-of-the-art. [ABSTRACT FROM AUTHOR]