A note on the approximability of cutting stock problems

Cutting stock problems and bin packing problems are basically the same problems. They differ essentially on the variability of the input items. In the first, we have a set of items, each item with a given multiplicity; in the second, we have simply a list of items (each of which we may assume to have multiplicity 1). Many approximation algorithms have been designed for packing problems; a natural question is whether some of these algorithms can be extended to cutting stock problems. We define the notion of “well-behaved” algorithms and show that well-behaved approximation algorithms for one, two and higher dimensional bin packing problems can be translated to approximation algorithms for cutting stock problems with the same approximation ratios.     

The recognition of a class of bifurcation problems

In bifurcation theory there are two recognition problems concerning a given normal form, the recognition for the normal form and the recognition for universal unfoldings of bifurcation problems which are equivalent to the normal form. The two recognition problems for the normal forms εx²+δλ^k were only partially solved. In this paper we give a complete solution of the two problems for all k?1 uniformly.     

Some fundamental problems of the theory of thermoviscoelasticity

Methods of solving quasistatic problems of the linear theory of thermoviscoelasticity are discussed. Special attention is given to the method of approximations. Modern methods of solving contact problems with a variable boundary and problems with a time-dependent boundary are briefly reviewed. Methods of solving problems with a nonuniform temperature field are outlined. The basic relations of the nonlinear theory of thermoviscoelasticity are given. Its various modifications and simplifications associated with the introduction of fairly general assumptions are examined. Methods of solving problems in certain nonlinear theories are noted. Nonisothermal (coupled) problems of thermoviscoelasticity and questions relating to the general theory with physical and geometric nonlinearity are discussed.Lomonosov Moscow State University. Translated from Mekhanika Polimerov, No. 1, pp. 41–58, January–February, 1971.     

NP-completeness of some problems of choosing a vector subset

The NP-completeness is proved of some problems of choosing a Euclidean vector subset. One of the data analysis problems is reduced to these problems. The required subset is assumed to have a fixed cardinality and include the vectors that are “close” to each other by the criterium of the minimum sum of squares of distances.     

Tractability of quasilinear problems I: General results

The tractability of multivariate problems has usually been studied only for the approximation of linear operators. In this paper we study the tractability of quasilinear multivariate problems. That is, we wish to approximate nonlinear operators S_d(·,·) that depend linearly on the first argument and satisfy a Lipschitz condition with respect to both arguments. Here, both arguments are functions of d variables. Many computational problems of practical importance have this form. Examples include the solution of specific Dirichlet, Neumann, and Schrödinger problems. We show, under appropriate assumptions, that quasilinear problems, whose domain spaces are equipped with product or finite-order weights, are tractable or strongly tractable in the worst case setting.This paper is the first part in a series of papers. Here, we present tractability results for quasilinear problems under general assumptions on quasilinear operators and weights. In future papers, we shall verify these assumptions for quasilinear problems such as the solution of specific Dirichlet, Neumann, and Schrödinger problems.     

Examples of max-flow and min-cut problems with duality gaps in continuous networks

Strang (Mathematical Programming 26, 1983) gave a method to establish a max-flow min-cut theorem in a domain of a Euclidean space. The method can be applied also to max-flow min-cut problems defined by Iri (Survey of Mathematical Programming, North-Holland, 1979) whenever the capacity functions of max-flow problems are bounded and continuous. This paper deals with max-flow min-cut problems of Strang and Iri with unbounded or noncontinuous capacity functions. It is proved that, in such problems, max-flow min-cut theorems may fail to hold.     

Conditions Characterizing Minima of the Difference of Functions

 Optimization problems involving differences of functions arouse interest as generalizations of so-called d.c. problems, i.e. problems involving the difference of two convex functions. The class of d.c. functions is very rich, so d.c. problems are rather general optimization problems. Several global optimality conditions for these d.c. problems have been proposed in the optimization literature. We provide a survey of these conditions and try to detect their common basis. This enables us to give generalizations of the conditions to situations when the objective function is no longer a difference of convex functions, but the difference of two functions which are representable as the upper envelope of an arbitrary family of functions. (Received 6 February 2001; in revised form 11 October 2001)     

Time complexity of single machine scheduling with stochastic precedence constraints

This paper deals with single machine scheduling problems with stochastic precedence relations (so calledGERT networks). Until now most investigations on such problems, dealt with algorithms running in polynomial time. On the other hand, for scheduling problems with deterministic precedence relations exist a lot of results about time complexity. Therefore, the object of this paper is to consider time complexity of scheduling problems with stochastic precedence constraints and to describe the boundary between theNP-hard problems and those which can be solved in polynomial time.     

Equivalence of Equilibrium Problems and Least Element Problems

In this paper, we introduce the concept of feasible set for an equilibrium problem with a convex cone and generalize the notion of a Z-function for bifunctions. Under suitable assumptions, we derive some equivalence results of equilibrium problems, least element problems, and nonlinear programming problems. The results presented extend some results of [Riddell, R.C.: Equivalence of nonlinear complementarity problems and least element problems in Banach lattices. Math. Oper. Res. 6, 462–474 (1981)] to equilibrium problems. This work was supported by the National Natural Science Foundation of China (10671135) and Specialized Research Fund for the Doctoral Program of Higher Education (20060610005) and the Educational Science Foundation of Chongqing (KJ051307).     

Computation of eigenvalues and solutions of regular Sturm–Liouville problems using Haar wavelets

The paper presents a novel method for the computation of eigenvalues and solutions of Sturm–Liouville eigenvalue problems (SLEPs) using truncated Haar wavelet series. This is an extension of the technique proposed by Hsiao to solve discretized version of variational problems via Haar wavelets. The proposed method aims to cover a wider class of problems, by applying it to historically important and a very useful class of boundary value problems, thereby enhancing its applicability. To demonstrate the effectiveness and efficiency of the method various celebrated Sturm–Liouville problems are analyzed for their eigenvalues and solutions. Also, eigensystems are investigated for their asymptotic and oscillatory behavior. The proposed scheme, unlike the conventional numerical schemes, such as Rayleigh quotient and Rayleigh–Ritz approximation, gives eigenpairs simultaneously and provides upper and lower estimates of the smallest eigenvalue, and it is found to have quadratic convergence with increase in resolution.     

Supporting the development of algebraic thinking in middle school: a closer look at students’ informal strategies

This study investigated how 31 sixth-, seventh-, and eighth-grade middle school students who had not previously, nor were currently taking a formal Algebra course, approached word problems of an algebraic nature. Specifically, these algebraic word problems were of the form x + (x + a) + (x + b) = c or ax + bx + cx = d. An examination of students’ understanding of the relationships expressed in the problems and how they used this information to solve problems was conducted. Data included the students’ written responses to problems, field notes of researcher-student interactions while working on the problems, and follow-up interviews. Results showed that students had many informal strategies for solving the problems with systematic guess and check being the most common approach. Analysis of researcher-student interactions while working on the problems revealed ways in which students struggled to engage in the problems. Support mechanisms for students who struggle with these problems are suggested. Finally, implications are provided for drawing upon students’ informal and intuitive knowledge to support the development of algebraic thinking.     

Optimal investment and reinsurance of an insurer with model uncertainty

We introduce a novel approach to optimal investment–reinsurance problems of an insurance company facing model uncertainty via a game theoretic approach. The insurance company invests in a capital market index whose dynamics follow a geometric Brownian motion. The risk process of the company is governed by either a compound Poisson process or its diffusion approximation. The company can also transfer a certain proportion of the insurance risk to a reinsurance company by purchasing reinsurance. The optimal investment–reinsurance problems with model uncertainty are formulated as two-player, zero-sum, stochastic differential games between the insurance company and the market. We provide verification theorems for the Hamilton–Jacobi–Bellman–Isaacs (HJBI) solutions to the optimal investment–reinsurance problems and derive closed-form solutions to the problems.     

Inverse scattering transforms and soliton solutions of nonlocal reverse-space nonlinear Schrödinger hierarchies

The aim of the paper is to construct nonlocal reverse-space nonlinear Schrödinger (NLS) hierarchies through nonlocal group reductions of eigenvalue problems and generate their inverse scattering transforms and soliton solutions. The inverse scattering problems are formulated by Riemann-Hilbert problems which determine generalized matrix Jost eigenfunctions. The Sokhotski-Plemelj formula is used to transform the Riemann-Hilbert problems into Gelfand-Levitan-Marchenko type integral equations. A solution formulation to special Riemann-Hilbert problems with the identity jump matrix, corresponding to the reflectionless transforms, is presented and applied to -soliton solutions of the nonlocal NLS hierarchies.     

Convergence of optimal controls in some optimization problems

We consider the behavior of bundles of optimal controls when the initial state of the system goes to some given vector. We investigate three types of optimization problems: problems with fixed process length and a free right endpoint; problems with fixed process length and a fixed right endpoint; time-optimal problems. The article is a review of recent results obtained by the author. __________ Translated from Nelineinaya Dinamika i Upravlenie, No. 4, pp. 301–314, 2004.     

Satisfiability of algebraic circuits over sets of natural numbers

We investigate the complexity of satisfiability problems for {∪,∩,⁻,+,×}-circuits computing sets of natural numbers. These problems are a natural generalization of membership problems for expressions and circuits studied by Stockmeyer and Meyer (1973) [10] and McKenzie and Wagner (2003) [8].Our work shows that satisfiability problems capture a wide range of complexity classes such as NL, P, NP, PSPACE, and beyond. We show that in several cases, satisfiability problems are harder than membership problems. In particular, we prove that testing satisfiability for {∩,+,×}-circuits is already undecidable. In contrast to this, the satisfiability for {∪,+,×}-circuits is decidable in PSPACE.     

Solution of projection problems over polytopes

Summary In this paper, we present variants of a convergent projection and contraction algorithm [25] for solving projection problems over polytope. By using the special struture of the projection problems, an iterative algorithm with constant step-size is given, which is globally linearly convergent. These algorithms are simple to implement and each step of the method requires only a few matrix-vector multiplications. Especially, for minimums norm problems over transportation or general network polytopes onlyO(n) additions andO(n) multiplications are needed at each iteration. Numerical results for randomly generated test problems over network polytopes, up to 10000 variables, indicate that the presented algorithms are simple and efficient even for large problems.     

Algebra Teachers' Utilization of Problems Requiring Transfer Between Algebraic,Numeric, and Graphic Representations

For students to develop an understanding of functions, they must have opportunities to solve problems that require them to transfer between algebraic, numeric, and graphic representations (transfer problems). Research has confirmed student difficulties with certain types of transfer problems and has suggested instructional factors as a possible cause. Algebra teachers (n= 28) were surveyed to determine the amount of class time they devote to different types of transfer problems and how many times these problems appear on their teacher‐made assessments. Results suggest that teachers dedicate less class time to graphic to numeric transfer problems than to any other type of transfer problem and that these problems appear less frequently on assessments. These are exactly the types of transfer problems that pose the most difficulty for students. It is conjectured that teachers' familiarity with these problems, combined with assumed student mastery, contribute to this mismatch.     

Problem posing via “what if not?” strategy in solid geometry — a case study

The study describes the kinds of problems posed by pre-service teachers on the basis of complex solid geometry tasks using the “what if not?” strategy and the educational value of such an activity. Twenty-eight pre-service teachers participated in two workshops in which they had to pose problems on the basis of given problems. Analysis of the posed problems revealed a wide range of problems including those containing a change of one of the numerical data to another specific one, to a proof problem. Different kinds of posed problems enlightened some phenomena such as a bigger frequency of posed problems with another numerical value and a lack of posed problems including formal generalization. We also discuss the educational strengths of problem posing in solid geometry using the “what if not?” strategy, which could make the learner rethink the geometrical concepts he uses while creating new problems, make connections between the given and the new concepts and as a result deepen his understanding of them.     

Minimax detection of a signal for nondegenerate loss functions, and extremal convex problems

We study a wide class of minimax problems of signal detection under nonparametric alternatives and a modification of these problems for a special class of loss functions. Under rather general assumptions, we obtain the exact asymptotics (of Gaussian type) for the minimax error probabilities and the structure of asymptotically minimax tests. The methods are based on a reduction of the problems under consideration to extremal problems of minimization of a certain Hilbert norm on a convex set of sequences of probability measures on the real line. These extremal problems are investigated in a paper by I. A. Suslina for alternatives having the type of l_q-ellipsoids with l_p-balls removed. Bibliography: 16 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 228, 1996, pp. 162–188.     

Bounded max-colorings of graphs

In a bounded max-coloring of a vertex/edge weighted graph, each color class is of cardinality at most b and of weight equal to the weight of the heaviest vertex/edge in this class. The bounded max-vertex/edge-coloring problems ask for such a coloring minimizing the sum of all color classes' weights. These problems generalize the well known max-coloring problems by taking into account the number of available resources (i.e., the cardinality of color classes) in practical applications. In this paper we present complexity results and approximation algorithms for the bounded max-coloring problems on general graphs, bipartite graphs and trees.