Search

In this short paper, we give an upper bound for the number of different basic feasible solutions generated by the simplex method for linear programming problems having optimal solutions. The bound is polynomial of the number of constraints, the number of variables, and the ratio between the minimum and the maximum values of all the positive elements of primal basic feasible solutions. When the primal problem is nondegenerate, it becomes a bound for the number of iterations. We show some basic results when it is applied to special linear programming problems. The results include strongly polynomiality of the simplex method for Markov Decision Problem by Ye and utilize its analysis., Comment: Keywords: Simplex method, Linear programming, Iteration bound, Strong polynomiality, Basic feasible solutions

Diaconis and Griffiths (2014) study the multivariate Krawtchouk polynomials orthogonal on the multinomial distribution. In this paper we derive the reproducing kernel orthogonal polynomials Q n ( x , y ; N , p ) on the multinomial distribution which are sums of products of orthonormal polynomials in x and y of fixed total degree n = 0 , 1 , … , N . The Poisson kernel ∑ n = 0 N ρ n Q n ( x , y ; N , p ) arises naturally from a probabilistic argument. An application to a multinomial goodness of fit test is developed, where the chi-squared test statistic is decomposed into orthogonal components which test the order of fit. A new duplication formula for the reproducing kernel polynomials in terms of the 1-dimensional Krawtchouk polynomials is derived. The duplication formula allows a Lancaster characterization of all reversible Markov chains with a multinomial stationary distribution whose eigenvectors are multivariate Krawtchouk polynomials and where eigenvalues are repeated within the same total degree. The χ 2 cutoff time, and total variation cutoff time is investigated in such chains. Emphasis throughout the paper is on a probabilistic understanding of the polynomials and their applications, particularly to Markov chains.

In this paper we make a comparison between certain probabilistic and deterministic point sets and show that some deterministic constructions (especially spherical t -designs) are better or as good as probabilistic ones like the jittered sampling model. We find asymptotic equalities for the discrete Riesz s -energy of sequences of well separated t -designs on the unit sphere S d ⊂ R d + 1 , d ≥ 2 . The case d = 2 was studied in Hesse (2009) and Hesse and Leopardi (2008). In Bondarenko et al., (2015) it was established that for d ≥ 2 , there exists a constant c d , such that for every N > c d t d there exists a well-separated spherical t -design on S d with N points. This paper gives results, based on recent developments that there exists a sequence of well separated spherical t -designs such that t and N are related by N ≍ t d .

In this paper we study the so called optimal polynomial meshes for domains in K ⊂ R d , d ≥ 2 . These meshes are discrete point sets Y n of cardinality c n d which have the property that ‖ p ‖ K ≤ A ‖ p ‖ Y n for every polynomial p of degree at most n with a constant A > 1 independent of n . It was conjectured earlier that optimal polynomial meshes exist in every convex domain. This statement was previously shown to hold for polytopes and C 2 like domains. In this paper we give a complete affirmative answer to the above conjecture when d = 2 .

Given an infinite family of extended real-valued functions fi, i∈I, and a family H of nonempty finite subsets of I, the H-partial robust sum of fi, i∈I, is the supremum, for J∈H, of the finite sums ∑j∈Jfj. These infinite sums arise in a natural way in location problems as well as in functional approximation problems, and include as particular cases the well-known sup function and the so-called robust sum function, corresponding to the set H of all nonempty finite subsets of I, whose unconstrained minimization was analyzed in previous papers of three of the authors (https://doi.org/10.1007/s11228-019-00515-2 and https://doi.org/10.1007/s00245-019-09596-9). In this paper, we provide ordinary and stable zero duality gap and strong duality theorems for the minimization of a given H-partial robust sum under constraints, as well as closedness and convex criteria for the formulas on the subdifferential of the sup-function. This research was supported by the National Foundation for Science & Technology Development (NAFOSTED), Vietnam, Project 101.01-2018.310, and by Ministerio de Ciencia, Innovación y Universidades (MCIU), Agencia Estatal de Investigación (AEI), and European Regional Development Fund (ERDF), Project PGC2018-097960-B-C22.

In this paper, we address the minimum-cost node-capacitated multiflow problem in an undirected network. For this problem, Babenko and Karzanov (2012) showed strongly polynomial-time solvability via the ellipsoid method. Our result is the first combinatorial weakly polynomial-time algorithm for this problem. Our algorithm finds a half-integral minimum-cost maximum multiflow in $O(m \log(nCD)\mathrm{SF}(kn, m, k))$ time, where $n$ is the number of nodes, $m$ is the number of edges, $k$ is the number of terminals, $C$ is the maximum node capacity, $D$ is the maximum edge cost, and $\mathrm{SF}(n', m', \eta)$ is the time complexity of solving the submodular flow problem in a network of $n'$ nodes, $m'$ edges, and a submodular function with $\eta$-time-computable exchange capacity. Our algorithm is built on discrete convex analysis on graph structures and the concept of reducible bisubmodular flows., Comment: A preliminary version of this paper was presented in at the 11th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, 2019

This paper studies the approximation of the Hilbert transform f ? = H f of continuous functions f with continuous conjugate f ? based on a finite number of samples. It is known that every sequence { H N f } N ? N which approximates f ? from samples of f diverges (weakly) with respect to the uniform norm. This paper conjectures that all of these approximation sequences even contain no convergent subsequence. A property which is termed strong divergence.The conjecture is supported by two results. First it is proven that the sequence of the sampled conjugate Fejer means diverges strongly. Second, it is shown that for every sample based approximation method { H N } N ? N there are functions f such that ? H N f ? ∞ exceeds any given bound for any given number of consecutive indices N .As an application, the later result is used to investigate a problem associated with a question of Ul'yanov on Fourier series which is related to the possibility to construct adaptive approximation methods to determine the Hilbert transform from sampled data. This paper shows that no such approximation method with a finite search horizon exists.

This paper provides the theoretical foundation for the component-by-component (CBC) construction of randomly shifted lattice rules that are tailored to integrals over R s arising from practical applications. For an integral of the form ∫ R s f ( y ) ∏ j = 1 s ϕ ( y j ) d y with a univariate probability density ϕ , our general strategy is to first map the integral into the unit cube [ 0 , 1 ] s using the inverse of the cumulative distribution function of ϕ , and then apply quasi-Monte Carlo (QMC) methods. However, the transformed integrand in the unit cube rarely falls within the standard QMC setting of Sobolev spaces of functions with mixed first derivatives. Therefore, a non-standard function space setting for integrands over R s , previously considered by Kuo, Sloan, Wasilkowski and Waterhouse (2010), is required for the analysis. Motivated by the needs of three applications, the present paper extends the theory of the aforementioned paper in several non-trivial directions, including a new error analysis for the CBC construction of lattice rules with general non-product weights, the introduction of an unanchored variant for the setting, the use of coordinate-dependent weight functions in the norm, and the strategy for fast CBC construction with POD (“product and order dependent”) weights.

This paper studies an extended trust region subproblem (eTRS) in which the trust region intersects the unit ball with $$m$$ m linear inequality constraints. When $$m=0,\,m = 1$$ m = 0 , m = 1 , or $$m = 2$$ m = 2 and the linear constraints are parallel, it is known that the eTRS optimal value equals the optimal value of a particular convex relaxation, which is solvable in polynomial time. However, it is also known that, when $$m \ge 2$$ m ? 2 and at least two of the linear constraints intersect within the ball, i.e., some feasible point of the eTRS satisfies both linear constraints at equality, then the same convex relaxation may admit a gap with eTRS. This paper shows that the convex relaxation has no gap for arbitrary $$m$$ m as long as the linear constraints are non-intersecting.

We investigate the ratio asymptotic behavior of the sequence $(Q_{n})_{n=0}^{\infty}$ of multiple orthogonal polynomials associated with a Nikishin system of $p\geq 1$ measures that are compactly supported on the star-like set of $p+1$ rays $S_{+}=\{z\in\mathbb{C}: z^{p+1}\geq 0\}$. The main algebraic property of these polynomials is that they satisfy a three-term recurrence relation of the form $zQ_{n}(z)=Q_{n+1}(z)+a_{n} Q_{n-p}(z)$ with $a_{n}>0$ for all $n\geq p$. Under a Rakhmanov-type condition on the measures generating the Nikishin system, we prove that the sequence of ratios $Q_{n+1}(z)/Q_{n}(z)$ and the sequence $a_{n}$ of recurrence coefficients are limit periodic with period $p(p+1)$. Our results complement some results obtained by the first author and Mi\~{n}a-D\'{i}az in a recent paper in which algebraic properties and weak asymptotics of these polynomials were investigated. Our results also extend some results obtained by the first author in the case $p=2$., Comment: Minor corrections were done for this version. A continuation of this work is in arXiv: 1907.03002. This paper has 37 pages, 1 table, no figures

A cutting-plane procedure for integer programming (IP) problems usually involves invoking a black-box procedure (such as the Gomory–Chvatal procedure) to compute a cutting-plane. In this paper, we describe an alternative paradigm of using the same cutting-plane black-box. This involves two steps. In the first step, we design an inequality $$cx \le d$$ where $$c$$ and $$d$$ are integral, independent of the cutting-plane black-box. In the second step, we verify that the designed inequality is a valid inequality by verifying that the set $$P \cap \{x\in \mathbb R ^n \mid cx \ge d + 1\} \cap \mathbb Z ^n$$ is empty using cutting-planes from the black-box. Here $$P$$ is the feasible region of the linear-programming relaxation of the IP. We refer to the closure of all cutting-planes that can be verified to be valid using a specific cutting-plane black-box as the verification closure of the considered cutting-plane black-box. This paper undertakes a systematic study of properties of verification closures of various cutting-plane black-box procedures.

In this paper we discuss a problem of generalization of binomial distributed triangle, that is sequence A287326 in OEIS. The main property of A287326 that it returns a perfect cube n as sum of n-th row terms over k, 0 or 1 , by means of its symmetry. In this paper we have derived a similar triangles in order to receive powers m=5,7 as row items sum and generalized obtained results in order to receive every odd-powered monomial n2m+1, m as sum of row terms of corresponding triangle. This version might be out of date, proceed by the link to see actual version., 16 pages, 8 figures, 2 tables, typos revised, added missing references, results generalized and shortened, derivations detailed.

In this paper we study the t-branch split cuts introduced by Li and Richard (Discret Optim 5:724–734, 2008). They presented a family of mixed-integer programs with n integer variables and a single continuous variable and conjectured that the convex hull of integer solutions for any n has unbounded rank with respect to (n−1)-branch split cuts. It was shown earlier by Cook et al. (Math Program 47:155–174, 1990) that this conjecture is true when n = 2, and Li and Richard proved the conjecture when n = 3. In this paper we show that this conjecture is also true for all n > 3.

This paper presents a procedure to solve the classical location median problem where the distances are measured with lp-norms with p > 2. In order to do that we consider an approximated problem. The global convergence of the sequence generated by this iterative scheme is proved. Therefore, this paper closes the still open question of giving a modification of the Weiszfeld algorithm that converges to an optimal solution of the median problem with lp norms and \({p \in (2, \infty)}\). The paper ends with a computational analysis of the different provided iterative schemes.

In the present paper, we study conditions under which the metric projection of a polyhedral Banach space X onto a closed subspace is Hausdorff lower or upper semicontinuous. For example, we prove that if X satisfies (*) (a geometric property stronger than polyhedrality) and Y@?X is any proximinal subspace, then the metric projection P"Y is Hausdorff continuous and Y is strongly proximinal (i.e., if {y"n}@?Y, x@?X and @?y"n-x@?->dist(x,Y), then dist(y"n,P"Y(x))->0). One of the main results of a different nature is the following: if X satisfies (*) and Y@?X is a closed subspace of finite codimension, then the following conditions are equivalent: (a) Y is strongly proximinal; (b) Y is proximinal; (c) each element of Y^@? attains its norm. Moreover, in this case the quotient X/Y is polyhedral. The final part of the paper contains examples illustrating the importance of some hypotheses in our main results.

Berrizbeitia and Olivieri showed in a recent paper that, for any integer r, the notion of @w-prime to base a leads to a primality test for numbers n=1 mod r, that under the Extended Riemann Hypothesis (ERH) runs in polynomial time. They showed that the complexity of their test is at most the complexity of the Miller primality test (MPT), which is O((logn)^4^+^o^(^1^)). They conjectured that their test is more effective than the MPT if r is large. In this paper, we show that their conjecture is not true by showing that the Berrizbeitia-Olivieri primality test (BOPT) has no advantage over the MPT, either for proving primality of a prime under the ERH, or for detecting compositeness of a composite. In particular, we point out that the complexity of the BOPT depends not only on n but also on r and that in the worst cases (usually when n is prime) for both tests, the BOPT is in general at least twice slower than the MPT, and in some cases (usually when n is composite) the BOPT may be much slower. Moreover, the BOPT needs O(rlogn) bit memories. We also give facts and numerical examples to show that, for some composites n and for some r, the rth roots of unity @w do not exist, and thus outputs of the BOPT are ERH conditional, whereas the MPT always quickly and definitely (without ERH) detects compositeness for all odd composites.

In a paper Cheung, Cucker and Peña (in press) [5] that can be seen as the first part of this one, we extended the well-known condition numbers for polyhedral conic systems C(A) Renegar (1994, 1995) [7–9] and C(A) Cheung and Cucker (2001) [3] to versions C¯(A) and C¯(A) that are finite for all input matrices A∈Rn×m. In this paper we compare C¯(A) and C¯(A) with other condition measures for the same problem that are also always finite.

The cyclic projections algorithm is an important method for determining a point in the intersection of a finite number of closed convex sets in a Hilbert space. That is, for determining a solution to the ''convex feasibility'' problem. This is the third paper in a series on a study of the rate of convergence for the cyclic projections algorithm. In the first of these papers, we showed that the rate could be described in terms of the ''angles'' between the convex sets involved. In the second, we showed that these angles often had a more tractable formulation in terms of the ''norm'' of the product of the (nonlinear) metric projections onto related convex sets. In this paper, we show that the rate of convergence of the cyclic projections algorithm is also intimately related to the ''linear regularity property'' of Bauschke and Borwein, the ''normal property'' of Jameson (as well as Bakan, Deutsch, and Li's generalization of Jameson's normal property), the ''strong conical hull intersection property'' of Deutsch, Li, and Ward, and the rate of convergence of iterated parallel projections. Such properties have already been shown to be important in various other contexts as well.

Many papers study polynomial tractability for multivariate problems. Let n(@?,d) be the minimal number of information evaluations needed to reduce the initial error by a factor of @? for a multivariate problem defined on a space of d-variate functions. Here, the initial error is the minimal error that can be achieved without sampling the function. Polynomial tractability means that n(@?,d) is bounded by a polynomial in @?^-^1 and d and this holds for all (@?^-^1,d)@?[1,~)xN. In this paper we study generalized tractability by verifying when n(@?,d) can be bounded by a power of T(@?^-^1,d) for all (@?^-^1,d)@[email protected], where @W can be a proper subset of [1,~)xN. Here T is a tractability function, which is non-decreasing in both variables and grows slower than exponentially to infinity. In this article we consider the set @W=[1,~)x{1,2,...,d^*}@?[1,@?"0^-^1)xN for some d^*>=1 and @?"[email protected]?(0,1). We study linear tensor product problems for which we can compute arbitrary linear functionals as information evaluations. We present necessary and sufficient conditions on T such that generalized tractability holds for linear tensor product problems. We show a number of examples for which polynomial tractability does not hold but generalized tractability does.

Suppose that X- = (X 0 , X 1 ) and Y-=(Y 0 ,Y 1 ) are Banach couples and suppose that T 0 : X 0 → Y 0 and T 1 : X 1 → Y 1 are bounded and linear. Also assume that Γ ∈ (Δ(X-))' and that T 0 and T 1 agree as maps from Δ(X-) ∩ ker Γ to Σ(Y-). If the maps do not agree as maps from all of Δ(X-) we cannot interpolate T 0 and T 1 to a map T : J 0,p (X- → J 0,p (Y-), where J 0,p denotes the classical J-method. This situation can for example be found in an article on interpolation of Hardy-type inequalities by Krugljak, Maligranda and Persson. We will in this paper define functors J 0,p;Γ such that T 0 and T 1 interpolate to a map T: J 0,p:Γ (X-) → J 0,p (Y-). The main purpose of this paper is to make the definition of the J 0,p;Γ (X-) spaces and build a theory for them. We will also do this for more general real parameters. If Γ is bounded on X 0 it holds that J 0,p:Γ (X-)=J 0,p (X 0 ∩ ker Γ, X 1 ). These spaces have been studied by Kalton, Ivanov and Lofstrom. Their results will follow as corollaries to the more general results of this article and our new theory can be thought of as a theory for generalized subcouples of codimension one. In the last section, we apply our theory to a situation considered by Krugljak, Maligranda and Persson in connection with Hardy-type inequalities. We prove new results and provide a new way of understanding that kind of problems.

Let Q: R → R be even, nonnegative and continuous, Q' be continuous, Q' > 0 in (0, ∞), and let Q'' be continuous in (0, ∞). Furthermore, Q satisfies further conditions. We consider a certain generalized Freud-type weight WrQ2(x) = |x|2r exp(-2Q(x)). In previous paper (J. Approx. Theory 121 (2003) 13) we studied the properties of orthonormal polynomials {Pn(WrQ2; x)}n=0x with the generalized Freud-type weight WrQ2(x) on R. In this paper we treat three themes. Firstly, we give an estimate of Pn(WrQ2; x) in the Lp-space, 0 < p ≤ ∞. Secondly, we obtain the Markov inequalities, and third we study the higher-order Hermite Fejer interpolation polynomials based at the zeros {xkn}k=1n of Pn(WrQ2; x). In Section 5 we show that our results are applicable to the study of approximation for continuous functions by the higher-order Hermite-Fejer interpolation polynomials.

Consider the Hardy-type integral operator T : Lp(a,b) → Lp(a,b), -∞ ≤ a < b ≤ ∞, which is defined by (Tf)(x) = v(x) ∫ax u(t)f(t)dt.In the papers by Edmunds et al. (J. London Math. Soc. (2) 37 (1988) 471) and Evans et al. (Studia Math. 130 (2) (1998) 171) upper and lower estimates and asymptotic results were obtained for the approximation numbers an(T) of T. In case p = 2 for "nice" u and v these results were improved in Edmunds et al. (J. Anal. Math. 85 (2001) 225). In this paper, we extend these results for 1 < p < ∞ by using a new technique. We will show that under suitable conditions on u and v, lim supn → ∞ n1/2 |λp-1/p ∫ab |u(t)v(t)|dt - nan(T)| ≤ c(||u'||p'/(p'+1) + ||v'||p/(p+1))(||u||p' + ||v||p) + 3αp||uv||1, where ||w||p = (∫ab |w(t)|p dt)1/p and λp is the first eigenvalue of the p-Laplacian eigenvalue problem on (0, 1).

We exhibit a new method for showing lower bounds for time-space tradeoffs of polynomial evaluation procedures given by straight-line programs. From the tradeoff results obtained by this method we deduce lower space bounds for polynomial evaluation procedures running in optimal nonscalar time. Time, denoted by L, is measured in terms of nonscalar arithmetic operations and space, denoted by S, is measured by the maximal number of pebbles (registers) used during the given evaluation procedure. The time-space tradeoff function considered in this paper is LS2. We show that for "almost all" univariate polynomials of degree at most d our time-space tradeoff functions satisfy the inequality LS2≥d8. From this we conclude that for "almost all" degree d univariate polynomials, any nonscalar time optimal evaluation procedure requires space at least S≥cd, where c>0 is a suitable universal constant. The main part of this paper is devoted to the exhibition of specific families of univariate polynomials which are "hard to compute" in the sense of time-space tradeoff (this means that our tradeoff function increases linearly in the degree). © 2000 Academic Press. Fil:Matera, G. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.

We consider the problem of approximating fixed points of contractive functions whose contraction factor is close to 1. In a previous paper (1993, K. Sikorski et al. , J. Complexity 9 , 181–200), we proved that for the absolute error criterion, the upper bound on the number of function evaluations to compute e -approximations is O( n 3 (ln(1/ e )+ln(1/(1− q ))+ln n )) in the worst case, where 0 q n is the dimension of the problem. This upper bound is achieved by the circumscribed ellipsoid (CE) algorithm combined with a dimensional deflation process. In this paper we present an inscribed ellipsoid (IE) algorithm that enjoys O( n (ln(1/ e )+ln(1/(1− q )))) bound. For q close to 1, the IE algorithm thus runs in many fewer iterations than the simple iteration method, that requires ⌈ln(1/ e )/ln(1/ q )⌉ function evaluations. Our analysis also implies that: (1) The dimensional deflation procedure in the CE algorithm is not necessary and that the resulting “plain” CE algorithm enjoys O( n 2 (log(1/ e )+log(1/(1− q )))) upper bound on the number of function evaluations. (2) The IE algorithm solves the problem in the residual sense, i.e., computes x such that ‖ f ( x )− x ‖⩽ δ , with O( n ln(1/ δ )) function evaluations for every q ⩽1.

It is known that if f ∈ W k p , then ω m ( f , t ) p ⩽ tω m −1 ( f ′, t ) p ⩽…. Its inverse with any constants independent of f is not true in general. Hu and Yu proved that the inverse holds true for splines S with equally spaced knots, thus ω m ( S , t ) p ∼ tω m −1 ( S ′, t ) p ∼ t 2 ω m −2 ( S ″, t ) p …. In this paper, we extend their results to splines with any given knot sequence, and further to principal shift-invariant spaces and wavelets under certain conditions. Applications are given at the end of the paper.

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.

Slater introduced the point-addition operation on graphs to characterize 4-connected graphs. The $$\varGamma $$ -extension operation on binary matroids is a generalization of the point-addition operation. In this paper, for a given binary matroid M we characterize the closure operator and the flats of the $$\varGamma $$ -extension binary matroid $$M^X$$ in terms of the closure operator of original binary matroid M.

The edge-connectivity of a connected hypergraph H is the minimum number of edges (named as edge-cut) whose removal makes H disconnected. It is known that the edge-connectivity of a hypergraph is bounded above by its minimum degree. H is super edge-connected, if every edge-cut consists of edges incident with a vertex of minimum degree. A hypergraph H is linear if any two edges of H share at most one vertex. We call H uniform if all edges of H have the same cardinality. Sufficient conditions for equality of edge-connectivity and minimum degree of graphs and super edge-connected graphs are known. In this paper, we present a generalization of some of these sufficient conditions to linear and/or uniform hypergraphs.

A finite group $${{{\mathbb {G}}}}$$ is said to have perfect order subsets if for every d, the number of elements of $$ {{{\mathbb {G}}}}$$ of order d (if there are any) divides $$|{{{\mathbb {G}}}}|.$$ In this paper, we make a modest improvement on the result of Ford, Konyagin and Luca [3] about perfect order subsets.

We show that if the Generalized Riemann Hypothesis is true, the problem of deciding whether a system of polynomial equations in several complex variables has a solution is in the second level of the polynomial hierarchy. In fact, this problem is in AM, the ``Arthur-Merlin'''' class (recall that $\np \subseteq \am \subseteq \rp^{\tiny \np} \subseteq \Pi_2$). The best previous bound was PSPACE. An earlier version of this paper was distributed as NeuroCOLT Technical Report~96-44. The present paper includes in particular a new lower bound for unsatisfiable systems, and remarks on the Arthur-Merlin class.

For two nonzero polynomialsformula]the successive signed Euclidean division yields algorithms, that is, semialgebraic computation trees, for tasks such as computing the sequence of successive quotients, deciding the signs of the sequence of remainders in a pointa?R, deciding the number of remainders, or deciding the degree pattern of the sequence of remainders. In this paper we show lower bounds of ordermlog2(m) for these tasks, within the computational framework of semi-algebraic computation trees. The inevitably long paths in semi-algebraic computation trees can be specified as those followed by certain prime cones in the real spectrum of a polynomial ring. We give in the paper a positive answer to the question posed in T. Lickteig (J. Pure Appl. Algebra110(2), 131?184 (1996)) whether the degree of the zero-set of the support of a prime cone provides a lower bound on the complexity of isolating the prime cone. The applications are based on the degree inequalities given by Strassen and Schuster and extend their work to the real situation in various directions.

Several recent papers have shown that some properties of the maximum weight stable set problem hold true in the more general setting of binary integer programs with two variables per inequality. In this paper, we show that in fact the two problems are equivalent by using the transitive closure of the binary integer program and (possibly) reducing the number of variables by fixing, complementing, or identifying them. We use this equivalence to prove two conjectures made by Johnson and Padberg regarding the perfection of bidirected graphs.

In a recent paper by Hu it is proved that for any convex function f there is a C 1 convex quadratic spline s with n knots that approximates f at the rate of ω 3 ( f , n −1 ). The knots of the spline are basically equally spaced. In this paper we give a simple construction of such a spline with equally spaced knots.

In this paper, we establish a non-trivial upper bound for the exponential sum $$\begin{aligned} \sum _{y

In this paper we characterize, in terms of their conjugacy classes, linear groups G such that $$G/\zeta _k(G)$$ G / ζ k ( G ) belongs to a certain group class $$\mathfrak {X}$$ X for several natural choices of $$\mathfrak {X}$$ X . Moreover, a description is given of linear groups with restrictions on layers.

In this paper, we prove the strong log-concavity and the unimodality of the various sequences of an extension of elementary symmetric function. The principal technique used is a combinatorial interpretation of determinants using lattice paths due to Gessel and Viennot. As applications, we establish the strong q-log-concavity and the unimodality of q-bi $$^{s}$$ nomial coefficients and their sequences lying on rays of the associated triangle.

There is no known formula that counts the number of transitive relations on a set with n elements. In this paper, it is shown that no polynomial in n with integer coefficients can represent a formula for the number of transitive relations on a set with n elements. Several inequalities giving various useful recursions and lower bounds on the number of transitive relations on a set are also proved.

In this paper, we continue the study of Lebesgue-type inequalities for greedy algorithms. We introduce the notion of strong partially greedy Markushevich bases and study the Lebesgue-type parameters associated with them. We prove that this property is equivalent to that of being conservative and quasi-greedy, extending a similar result given in Dilworth et al. (Constr Approx 19:575–597, 2003) for Schauder bases. We also give a characterization of 1-strong partial greediness, following the study started in Albiac and Ansorena (Rev Matem Compl 30(1):13–24, 2017), Albiac and Wojtaszczyk (J Approx Theory 138:65–86, 2006).

Previous work on the ϵ-complexity of elliptic boundary-value problems Lu = f assumed that the class F of problem elements f was the unit ball of a Sobolev space. In a recent paper, we considered the case of a model two-point boundary-value problem, with F being a class of analytic functions. In this paper, we ask what happens if F is a class of piecewise analytic functions. We find that the complexity depends strongly on how much a priori information we have about the breakpoints. If the location of the breakpoints is known, then the "-complexity is proportional to ln（ϵ-1）, and there is a finite element p-method (in the sense of Babuska) whose cost is optimal to within a constant factor. If we know neither the location nor the number of breakpoints, then the problem is unsolvable for ϵ less than sqroot(2). If we know only that there are b equal or greater than 2 breakpoints, but we don't know their location, then the ϵ-complexity is proportional to bϵ-1, and a finite element h-method is nearly optimal. . In short, knowing the location of the breakpoints is as good as knowing that the problem elements are analytic, whereas only knowing the number of breakpoints is no better than knowing that the problem elements have a bounded derivative in the L2 sense.

A radial basis function approximation has the form [formula] where φ: [0,∞)→ R is some given function, (yj)n1 are real coefficients, and the centres (xj)n1 are points in Rd. For a wide class of functions φ, it is known that the interpolation matrix A = (φ(||xj − xk||2))nj,k=1 is invertible. Further, several recent papers have provided upper bounds on ||A−1||2, where the points (xj)n1 satisfy the condition ||xj − xk||2 ≥ δ, j ≠ k, for some positive constant δ. In this paper, we provide the least upper bound on ||A−1||2 when the points (xj)n1 form any subset of the integer lattice Ld, and when φ is a conditionally negative definite function of order 1, a large set of functions which includes the multiquadric. Specifically, for any set of points (xj)n1 ⊂ Ld, we provide the inequality [formula] where e = [1, . . . , 1]T ∈ Rd and where φ̂ is the generalized Fourier transform of φ. We provide a constructive proof that no smaller bound is valid and comment on the relevance of the method of analysis to the problem of estimating all the eigenvalues of such an interpolation matrix

The paper considers Hermite interpolation for vector-valued functions. Corresponding to the interpolating functions f we define functionals I which contain function values of f ( r ) and integrals of f ( r ) where 0 ≤ r ≤ m for some integer m . The main purpose of the paper is to characterize those functions which satisfy the interpolation problem and have a minimal value of I . These characterizations contain several results of the literature including splines in tension and geometric splines.

In Section 3.3 of the paper [3], we compare our nonlinear separation model (MIR-SEP) for MIR cuts with the one for split cuts (PMILP) presented in Balas and Saxena [1] and show that (Lemma 9) they are equivalent. We then present a numerical example to show that the linearized separation models are not equivalent and make the following claim without a proof: “The Balas/Saxena model PMILP for this example (or more precisely, the deparametrized model MILP(θ )) is infeasible unless the parameter θ is chosen to be exactly 0.31.” This claim is incorrect (as pointed out to us by Balas and Saxena) and contains two errors. The first is that Balas and Saxena [1] assume that all variables are non-negative, whereas the example in our paper contains a free variable. Secondly, for any problem in the correct format (including the one obtained by replacing the free variable in our example by two non-negative variables) MILP(θ ) is feasible for all θ ∈ (0, 1).

The probabilistic setting for approximately solved problems has been studied in a number of papers; see, e.g., (Lee and Wasilkowski, 1986; Traub et al., 1988) and papers cited therein. Roughly speaking, it can be described in the following way. Suppose that we want to approximate the solutions SY-, for f E F, where S: F + G is an operator, F is a linear space, and G is a normed linear space. The elements S(j) are approximated by Ucf) E G, where Ucf) = 4(Ncf)) with information Ncf) consisting of n values of linear functionals Liv), and with an algorithm 4: N(F) + G being an arbitrary mapping. Assuming that the space F is endowed with a given probability measure /,L, the quality of U = 4 0 N is measured by the p-probability that the error [IS(j) U(‘j)ll is small. That is, for a given parameter 6 E (0, l), we seek an “optimal” algorithm U that, with probability at least 1 6, approximates Scf) to within E for as small E as possible. Equivalently: for a given 6 E (0, l), we want to find a pair (U, E) such that E is the smallest number for which p(CfE F: [IS(~) U(j)II 5 E}) 2 1 6. Since the bound E is independent off, it is an a priori bound. Since we seek the smallest E, in the probabilistic setting we actually search for U = $J 0 N that admits the sharpest a priori error bounds. In this paper, we propose a more general approach by permitting a posteriori bounds. That is, in addition to algorithms $, we let bounds Bcf

A simple undirected graph $$\Gamma _G$$ whose vertex set is the set of non-central elements of a finite group G and two vertices x and y are adjacent if they commute is called commuting graph of G. In this paper, we compute energy, Laplacian energy and signless Laplacian energy of $$\Gamma _G$$ for some classes of super integral groups.

In this paper, we introduce the generalized dual hyperbolic Fibonacci numbers. As special cases, we deal with dual hyperbolic Fibonacci and dual hyperbolic Lucas numbers. We present Binet's formulas, generating functions and the summation formulas for these numbers. Moreover, we give Catalan's, Cassini's, d'Ocagne's, Gelin-Cesàro's, Melham's identities and present matrices related with these sequences.

We present in this paper alternating linearization algorithms based on an alternating direction augmented Lagrangian approach for minimizing the sum of two convex functions. Our basic methods require at most $${O(1/\epsilon)}$$ iterations to obtain an $${\epsilon}$$ -optimal solution, while our accelerated (i.e., fast) versions of them require at most $${O(1/\sqrt{\epsilon})}$$ iterations, with little change in the computational effort required at each iteration. For both types of methods, we present one algorithm that requires both functions to be smooth with Lipschitz continuous gradients and one algorithm that needs only one of the functions to be so. Algorithms in this paper are Gauss-Seidel type methods, in contrast to the ones proposed by Goldfarb and Ma in (Fast multiple splitting algorithms for convex optimization, Columbia University, 2009) where the algorithms are Jacobi type methods. Numerical results are reported to support our theoretical conclusions and demonstrate the practical potential of our algorithms.

The graphical relaxation of the Traveling Salesman Problem is the relaxation obtained by requiring that the salesman visit each city at least once instead of exactly once. This relaxation has already led to a better understanding of the Traveling Salesman polytope in Cornuejols, Fonlupt and Naddef (1985). We show here how one can compose facet-inducing inequalities for the graphical traveling salesman polyhedron, and obtain other facet-inducing inequalities. This leads to new valid inequalities for the Symmetric Traveling Salesman polytope. This paper is the first of a series of three papers on the Symmetric Traveling Salesman polytope, the next one studies the strong relationship between that polytope and its graphical relaxation, and the last one applies all the theoretical developments of the two first papers to prove some new facet-inducing results.

This paper presents extensions and further analytical properties of algorithms for linear programming based only on primal scaling and projected gradients of a potential function. The paper contains extensions and analysis of two polynomial-time algorithms for linear programming. We first present an extension of Gonzaga's O(nL) iteration algorithm, that computes dual variables and does not assume a known optimal objective function value. This algorithm uses only affine scaling, and is based on computing the projected gradient of the potential function $$q\ln (x^T s) - \sum\limits_{j = 1}^n {\ln (x_j )} $$ wherex is the vector of primal variables ands is the vector of dual slack variables, and q = n + $$\sqrt n $$ . The algorithm takes either a primal step or recomputes dual variables at each iteration. We next present an alternate form of Ye's O( $$\sqrt n $$ L) iteration algorithm, that is an extension of the first algorithm of the paper, but uses the potential function $$q\ln (x^T s) - \sum\limits_{j = 1}^n {\ln (x_j ) - \sum\limits_{j - 1}^n {\ln (s_j )} } $$ where q = n + $$\sqrt n $$ . We use this alternate form of Ye's algorithm to show that Ye's algorithm is optimal with respect to the choice of the parameterq in the following sense. Suppose thatq = n + n t wheret⩾0. Then the algorithm will solve the linear program in O(n r L) iterations, wherer = max{t, 1 − t}. Thus the value oft that minimizes the complexity bound ist = 1/2, yielding Ye's O( $$\sqrt n $$ L) iteration bound.

The objective of this paper is to present a unified study of multivariate super vertex splines with emphasis on the construction procedure and an application to least-squares approximation with interpolatory constraints. Both simplicial and parallelepiped partitions are studied in some detail, and in the bivariate setting, even a partition consisting of both triangles and parallelograms is considered. When the polynomial degree is allowed to be sufficiently large as compared to the order of smoothness, it is clear that vertex splines can be constructed by working on each simplex or parallelepiped separately as long as certain suitable normal derivative constraints are imposed on the boundary faces. Our constructive procedure will take a different route. Instead of normal derivatives, we impose extra interpolatory conditions at the “vertices”. This gives rise to the notion of “super splines” introduced in this paper. It should also be emphasized that the view point of considering a basis of piecewise polynomials with smallest possible supports so that the full approximation order is preserved makes vertex splines different from the standard approach in finite elements. After all, if the polynomial degree is required to be lower, it is necessary to work on at least three adjacent simplices or parallelepipeds simultaneously in constructing a basis of vertex splines.

In a recent paper Tardos described a polynomial algorithm for solving linear programming problems in which the number of arithmetic steps depends only on the size of the numbers in the constraint matrix and is independent of the size of the numbers in the right hand side and the cost coefficients. In this paper we extend Tardos' results and present a polynomial algorithm for solving strictly convex quadratic programming problems in which the number of arithmetic steps is independent of the size of the numbers in the right hand side and the linear cost coefficients.