A General Darboux-Type Boundary Value Problem in Curvilinear Domains with Corners for a Third-Order Equation with Dominated Lower-Order Terms

We study solvability of the Darboux-type boundary value problem for a third-order linear partial differential equation with dominated lower-order terms. We indicate function spaces in which the problem is uniquely solvable and Hausdorff normally solvable. In the second case, the corresponding homogeneous problem is shown to have infinitely many linearly independent solutions.     

Group Embeddings with Algorithmic Properties

We show that every countable group H with solvable word problem can be subnormally embedded into a 2-generated group G which also has solvable word problem. Moreover, the membership problem for H < G is also solvable. We also give estimates of time and space complexity of the word problem in G and of the membership problem for H < G.     

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.     

Classical r-Matrices and Novikov Algebras

We study the existence problem for Novikov algebra structures on finite-dimensional Lie algebras. We show that a Lie algebra admitting a Novikov algebra is necessarily solvable. Conversely we present a 2-step solvable Lie algebra without any Novikov structure. We use extensions and classical r-matrices to construct Novikov structures on certain classes of solvable Lie algebras.     

Single-machine scheduling simultaneous with position-based and sum-of-processing-times-based learning considerations under group technology assumption

This paper considers the problems of scheduling with the effect of learning on a single-machine under group technology assumption. We propose a new learning model where the job actual processing time is linear combinations of the scheduled position of the job and the sum of the normal processing time of jobs already processed. We show that the makespan minimization problem is polynomially solvable. We also prove that the total completion time minimization problem with the group availability assumption remains polynomially solvable under agreeable conditions.     

Occurrence problem for free solvable groups

We study the problem on the existence of an algorithm verifying whether systems of linear equations over a group ring of a free metabelian group are solvable. The occurrence problem for free solvable groups of derived length 3is proved undecidable. We give an example of a group with undecidable word problem which is finitely presented in a variety of solvable groups and is defined by the relations from the last commutator subgroup. Translated fromAlgebra i Logika, Vol. 34, No. 2, pp. 211-232, March-April, 1995.     

Gellerstedt problem with nonclassical matching conditions for the solution gradient on the type change line with data on internal characteristics

We study the solvability of the Gellerstedt problem for the Lavrent’ev–Bitsadze equation. An initial function is posed in the ellipticity domain of the equation on the boundary of the unit half-circle with center the origin. Zero conditions are posed on characteristics in the hyperbolicity domain of the equation. “Frankl-type conditions” are posed on the type change line of the equation. We show that the problem is either conditionally solvable or uniquely solvable. We obtain a closed-form solvability condition in the case of conditional solvability. We derive integral representations of the solution in all cases.     

Boundary-Value Problem for Functional-Differential Advanced-Retarded Tricomi Equation

We investigate the boundary-value problem for Tricomi mixed-type equation with multiple functional retarding and advancing. We construct the general solution to the equation. The problem is uniquely solvable.     

Tricomi problem for a functional-differential advanced-retarded Lavrent’ev–Bitsadze equation

We study a boundary value problem for the Lavrent’ev–Bitsadze equation with functional delay and advance. The general solution is constructed. The problem is uniquely solvable.     

Due-date assignment on uniform machines

The classical weighted minsum scheduling and due-date assignment problem (with earliness, tardiness and due-date costs) was shown to be polynomially solvable on a single machine, more than two decades ago. Later, it was shown to have a polynomial time solution in the case of identical processing time jobs and parallel identical machines. We extend the latter setting to parallel uniform machines. We show that the two-machine case is solved in constant time. Furthermore, the problem remains polynomially solvable for a given (fixed) number of machines.     

Feasibility and Solvability for Vector Complementarity Problems1

The purpose of this paper is to discuss the feasibility and solvability of vector complementarity problems. We prove that, under suitable conditions, the vector complementarity problem with a pseudomonotonicity assumption is solvable whenever it is strictly feasible. By strengthening the generalized monotonicity condition, we show also that the homogeneous vector complementarity problem is solvable whenever it is feasible. At last, we study the solvability of the vector complementarity problem on product spaces.The authors thank Professor Franco Giannessi for valuable comments and suggestions leading to improvements of this paper.     

Solvability of the Cauchy problem for linear operator-differential equations with variable operator coefficients

We study the Cauchy problem for linear operator-differential equations with unbounded, nondensely defined, variable operator coefficients in a Banach space. We single out new classes of evolution equations of first and second order for which the Cauchy problem is solvable.     

A nonlocal problem for a first-order partial differential equation

In this paper we study a nonlocal problem for a first-order partial differential equation with an integral condition instead of the standard boundary one. We prove that the problem under consideration is uniquely solvable.     

A well-solvable special case of the bounded knapsack problem

We identify a polynomially solvable special case of the bounded knapsack problem that is characterized by a set of simple inequalities relating item weight ratios to item profit ratios. Our result generalizes and extends a corresponding result of Zukerman, et al. [M. Zukerman, L. Jia, T. Neame, G.J. Woeginger, A polynomially solvable special case of the unbounded knapsack problem, Operations Research Letters 29 (2001) 13-16] for the unbounded knapsack problem.     

工件带简单线性恶化函数和共同交货期单机排序问题

本文研究单机排序问题,其中工件加工时间具有简单线性恶化函数.同时,所有工件均具有一个给定共同交货期.目标函数为最小化提前有奖延误受罚之和.在逆一致性条件下,给出了求解该排序问题的一个伪多项式时间动态规划算法.同时借助于几何舍入技巧,对求解这类排序问题给出了一个充分多项式时间的近似算法(FPTAS)。     

Allocating procurement to capacitated suppliers with concave quantity discounts

We consider a procurement problem where suppliers offer concave quantity discounts. The resulting continuous knapsack problem involves the minimization of a sum of separable concave functions. We identify polynomially solvable special cases of this NP-hard problem, and provide a fully polynomial-time approximation scheme for the general problem.     

The normal sub-Riemannian geodesic flow on E(2) generated by a left-invariant metric and a right-invariant distribution

We consider a sub-Riemannian problem on the three-dimensional solvable Lie group E(2) endowed with a left-invariant metric and a right-invariant distribution. The problem is based on construction of a Hamilton structure for the given metric by the Pontryagin maximum principle.     

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.     

A new integral equation approach to the Neumann problem in acoustic scattering

We suggest a new approach of reduction of the Neumann problem in acoustic scattering to a uniquely solvable Fredholm integral equation of the second kind with weakly singular kernel. To derive this equation we placed an additional boundary with an appropriate boundary condition inside the scatterer. The solution of the problem is obtained in the form of a single layer potential on the whole boundary. The density in the potential satisfies a uniquely solvable Fredholm integral equation of the second kind and can be computed by standard codes. Copyright © 2001 John Wiley & Sons, Ltd.     

Tricomi Problem for Equations of Mixed Type with Iterated Functional Delay and Advance

We study the Tricomi problem for equations of mixed type with multiple functional delay and advance. A general solution of the equations is obtained. The problem is uniquely solvable.