The recovery of even polynomial potentials

We consider the problem of reconstructing an even polynomial potential from one set of spectral data of a Sturm-Liouville problem. We show that we can recover an even polynomial of degree 2m from m+1 given Taylor coefficients of the characteristic function whose zeros are the eigenvalues of one spectrum. The idea here is to represent the solution as a power series and identify the unknown coefficients from the characteristic function. We then compute these coefficients by solving a nonlinear algebraic system, and provide numerical examples at the end. Because of its algebraic nature, the method applies also to non self-adjoint problems.     

A certain polynomial of a graph and graphs with an extremal number of trees

The polynomial we consider here is the characteristic polynomial of a certain (not adjacency) matrix associated with a graph. This polynomial was introduced in connection with the problem of counting spanning trees in graphs [8]. In the present paper the properties of this polynomial are used to construct some classes of graphs with an extremal numbers of spanning trees.     

关于一道研究生入学考试线性代数题的探讨

从2020年全国硕士研究生入学考试的一道线性代数题的解法出发,考虑了一个更一般的关于矩阵特征多项式的问题,并对该问题给出了回答.     

On a problem with a shift and with the Frankl condition on a segment of the degeneration line for a class of equations of mixed type

We consider the Frankl-Nakhushev problem. By using the maximum principle, we prove the uniqueness of the solution of the problem in the class of Hölder functions, and by using the method of integral equations, in particular, the recently developed method of Wiener-Hopf equations, we prove its existence.     

On the factorization of polynomial matrices over the domain of principal ideals

We consider the problem of decomposition of polynomial matrices over the domain of principal ideals into a product of factors of lower degrees with given characteristic polynomials. We establish necessary and, under certain restrictions, sufficient conditions for the existence of the required factorization.     

Polynomial Algorithms for a Class of Discrete Minmax Linear Programming Problems

We consider the problem of obtaining integer solutions to a minmax linear programming problem. Although this general problem is NP-complete, it is shown that a restricted version of this problem can be solved in polynomial time. For this restricted class of problems two polynomial time algorithms are suggested, one of which is strongly polynomial whenever its continuous analogue and an associated linear programming problem can be solved by a strongly polynomial algorithm. Our algorithms can also be used to obtain integer solutions for the minmax transportation problem with an inequality budget constraint. The equality constrained version of this problem is shown to be NP-complete. We also provide some new insights into the solution procedures for the continuous minmax linear programming problem.     

The complexity of approximating a nonlinear program

We consider the problem of finding the maximum of a multivariate polynomial inside a convex polytope. We show that there is no polynomial time approximation algorithm for this problem, even one with a very poor guarantee, unless P = NP. We show that even when the polynomial is quadratic (i.e. quadratic programming) there is no polynomial time approximation unless NP is contained in quasi-polynomial time.Our results rely on recent advances in the theory of interactive proof systems. They exemplify an interesting interplay of discrete and continuous mathematics—using a combinatorial argument to get a hardness result for a continuous optimization problem.     

Eigenfunctions of Two-Scale Difference Equations with Dilation Parameter and Infinite Products

This paper deals with two-scale difference equations having an arbitrary dilation parameter and a formal power series as symbol. We investigate the equation concerning the existence of nonzero compactly supported distributional solutions. In order to include also continuous solutions it is advantageous to consider the two-scale difference equation as eigenvalue problem where the solutions are either compactly supported or integrals of compactly supported distributions. Such solutions are called eigenfunctions. As main result we determine the necessary and sufficient condition for the existence of eigenfunctions that the symbol must be a rational function with a special structure depending on the dilation parameter. We show that the eigenfunctions can be expressed by means of a finite sum of shifted eigenfunctions belonging to the case with a polynomial symbol (characteristic polynomial), which is well investigated.     

On degree sequence optimization

We consider the problem of finding a subgraph of a given graph maximizing a given function evaluated at its degree sequence. While it is intractable already for convex functions, we show it is polynomial time solvable for convex multi-criteria objectives. We also consider a colored extension of the problem with separable objectives, which includes the notorious exact matching problem as a special case, and show that it is polynomial time solvable on graphs of bounded tree-depth for any vertex functions.     

The extremal function in the Delsarte problem of finding an upper bound for the kissing number in the three-dimensional space

We consider an extremal problem for continuous functions that are nonpositive on a closed interval and can be represented by series in Legendre polynomials with nonnegative coefficients. This problem arises from the Delsarte method of finding an upper bound for the kissing number in the three-dimensional Euclidean space. We prove that the problem has a unique solution, which is a polynomial of degree 27. This polynomial is a linear combination of Legendre polynomials of degrees 0, 1, 2, 3, 4, 5, 8, 9, 10, 20, and 27 with positive coefficients; it has simple root 1/2 and five double roots in (?1, 1/2). We also consider the dual extremal problem for nonnegative measures on [?1, 1/2] and, in particular, prove that an extremal measure is unique.     

Maximization of solution flexibility for robust shop scheduling

We consider the problem of introducing flexibility in the schedule determination phase, for shop scheduling problems with release dates and deadlines. The flexibility is provided by generating a family of schedules, instead of a unique one. We represent a family of schedules by an ordered group assignment defining for each machine a sequence of groups where the operations within a group are totally permutable. We propose a polynomial time algorithm to evaluate the worst case completion time of operations in an ordered group assignment. We then consider the single machine problem with heads and deadlines associated to operations, as a sub-problem of the job shop problem. We propose polynomial time dynamic programming algorithms for minimizing the number of groups and for maximizing the number of characterized sequences, under specific constraints. Finally, computational experiences on job shop benchmarks, show the impact of grouping operations on the solution makespan value.     

Identification of the polynomial in nonseparated boundary conditions by one eigenvalue

We consider a spectral problem for an ordinary differential equation on a finite interval. The boundary conditions contain functions and a polynomial in the spectral parameter. We find a criterion for the unique reconstruction of this polynomial by one multiple eigenvalue. Related examples are presented.     

Problème de Cauchy pour certaines équations du type de Schrödinger

We consider a 2-evolution operator in the sense of Petrowsky, and we assume that the characteristic roots of the principal polynomial with constant coefficients are real and of constant multiplicities. Then we give sufficient conditions so that the Cauchy problem both for the future and for the past is well-posed in the Sobolev spaces. Our conditions are analogous to the Levi conditions and to the decomposition conditions of operators in the hyperbolic case for Kowalewskian operators.     

On the routing open shop problem with two machines on a two-vertex network

The open shop problem is under study with two machines and routing on a two-vertex network. This problem is NP-hard. We introduce an exact pseudopolynomial algorithm, propose a fully polynomial time approximation scheme for solving this problem, and consider some particular polynomially solvable cases.     

Interpolating solutions of the Poisson equation in the disk based on Radon projections

We consider an algebraic method for reconstruction of a function satisfying the Poisson equation with a polynomial right-hand side in the unit disk. The given data, besides the right-hand side, is assumed to be in the form of a finite number of values of Radon projections of the unknown function. We first homogenize the problem by finding a polynomial which satisfies the given Poisson equation. This leads to an interpolation problem for a harmonic function, which we solve in the space of harmonic polynomials using a previously established method. For the special case where the Radon projections are taken along chords that form a regular convex polygon, we extend the error estimates from the harmonic case to this Poisson problem. Finally we give some numerical examples.     

Irregular boundary value problem for the Sturm–Liouville operator

We consider an eigenvalue problem for the Sturm–Liouville operator with nonclassical asymptotics of the spectrum. We prove that this problem, which has a complete system of root functions, is not almost regular (Stone-regular) but its Green function has a polynomial order of growth in the spectral parameter.     

Bernstein–Sato polynomials in positive characteristic

In characteristic zero, the Bernstein–Sato polynomial of a hypersurface can be described as the minimal polynomial of the action of an Euler operator on a suitable D-module. We consider analogous D-modules in positive characteristic, and use them to define a sequence of Bernstein–Sato polynomials (corresponding to the fact that we need to consider also divided powers Euler operators). We show that the information contained in these polynomials is equivalent to that given by the F-jumping exponents of the hypersurface, in the sense of Hara and Yoshida [N. Hara, K.-i. Yoshida, A generalization of tight closure and multiplier ideals, Trans. Amer. Math. Soc. 355 (2003) 3143–3174].     

Approximability of two-machine no-wait flowshop scheduling with availability constraints

We consider in this paper the two-machine no-wait flowshop scheduling problem in which each machine may have an unavailable interval. We present a polynomial time approximation scheme for the problem when the unavailable interval is imposed on only one machine, or the unavailable intervals on the two machines overlap.     

Scheduling parallel machines with inclusive processing set restrictions and job release times

We consider the problem of scheduling a set of jobs with different release times on parallel machines so as to minimize the makespan of the schedule. The machines have the same processing speed, but each job is compatible with only a subset of those machines. The machines can be linearly ordered such that a higher-indexed machine can process all those jobs that a lower-indexed machine can process. We present an efficient algorithm for this problem with a worst-case performance ratio of 2. We also develop a polynomial time approximation scheme (PTAS) for the problem, as well as a fully polynomial time approximation scheme (FPTAS) for the case in which the number of machines is fixed.     

A universality theorem for ratios of random characteristic polynomials

We consider asymptotics of ratios of random characteristic polynomials associated with orthogonal polynomial ensembles. Under some natural conditions on the measure in the definition of the orthogonal polynomial ensemble we establish a universality limit for these ratios.