On Bipartite and Multipartite Clique Problems

In this paper, we introduce the maximum edge biclique problem in bipartite graphs and the edge/node weighted multipartite clique problem in multipartite graphs. Our motivation for studying these problems came from abstractions of real manufacturing problems in the computer industry and from formal concept analysis. We show that the weighted version and four variants of the unweighted version of the biclique problem are NP-complete. For random bipartite graphs, we show that the size of the maximum balanced biclique is considerably smaller than the size of the maximum edge cardinality biclique, thus highlighting the difference between the two problems. For multipartite graphs, we consider three versions each for the edge and node weighted problems which differ in the structure of the multipartite clique (MPC) required. We show that all the edge weighted versions are NP-complete in general. We also provide a special case in which edge weighted versions are polynomially solvable.     

Set-valued versions of Ky Fan's inequality with application to variational inclusion theory

In this paper, we prove two set-valued versions of Ky Fan's minimax inequality. From these results, versions of Schauder's and Kakutani's fixed point theorems can be deduced. We formulate a variational inclusion problem for set-valued maps and a differential inclusion problem, concerning the contingent derivative. Sufficient conditions for the existence of solution for these inclusion problems are obtained, generalizing classical variational inequality problems.     

Benson type algorithms for linear vector optimization and applications

New versions and extensions of Benson’s outer approximation algorithm for solving linear vector optimization problems are presented. Primal and dual variants are provided in which only one scalar linear program has to be solved in each iteration rather than two or three as in previous versions. Extensions are given to problems with arbitrary pointed solid polyhedral ordering cones. Numerical examples are provided, one of them involving a new set-valued risk measure for multivariate positions.     

Geometric measures in the dual Brunn–Minkowski theory and their associated Minkowski problems

A longstanding question in the dual Brunn–Minkowski theory is “What are the dual analogues of Federer’s curvature measures for convex bodies?” The answer to this is provided. This leads naturally to dual versions of Minkowski-type problems: What are necessary and sufficient conditions for a Borel measure to be a dual curvature measure of a convex body? Sufficient conditions, involving measure concentration, are established for the existence of solutions to these problems.     

Parallel machine scheduling with high multiplicity

In high-multiplicity scheduling problems, identical jobs are encoded in the efficient format of describing one of the jobs and the number of identical jobs. Similarly, identical machines are efficiently encoded in the same manner. We investigate parallel-machine, high-multiplicity problems, where there are three possible machine speed structures: identical, proportional, or unrelated. For the objectives of minimizing the sum of job completion times and minimizing the makespan, we consider both nonpreemptive and preemptive problems. For some problems, we develop polynomial time algorithms. For several problems, we demonstrate that the recognition versions can be solved in polynomial time, while the optimization versions require pseudo-polynomial time. We also show that changing from standard binary encoding to high-multiplicity encoding does not affect the complexity class of NP-complete problems. Received: April 1996 / Accepted: July 2000?Published online January 17, 2001     

Differentiability in optimization theory 1

This paper deals with necessary conditions for optimization problems with infinitely many inequality constraints assuming various differentiability conditions. By introducing a second topology N on a topological vector space we define generalized versions of differentiability and tangential cones. Different choices of N lead to Gâteaux-, Hadamaed- and weak differentiability with corresponding tangential cones. The general concept is used to derive necessary conditions for local optimal points in form of inequalities and generalized multiplier rules, Special versions of these theorems are obtained for different differentiability assumptions by choosing properly. An application to approximation theory is given.     

A Relaxation of a Min-Cut Problem in an Anisotropic Continuous Network

Strang [18] introduced optimization problems on a Euclidean domain which are closely related with problems in mechanics and noted that the problems are regarded as continuous versions of famous max-flow and min-cut problems. In [15] we generalized the problems and called the generalized problems max-flow and min-cut problems of Strang's type. In this paper we formulate a relaxed version of the min-cut problem of Strang's type and prove the existence of optimal solutions under some suitable conditions. The conditions are essential. In fact, there is an example of the relaxed version which has no optimal solutions if the conditions are not fulfilled. We give such an example in the final section. Accepted 8 October 1998     

Some comments on preference order dynamic programming models

A simple deterministic dynamic programming model is used as a general framework for the analysis of stochastic versions of three classical optimization problems: knapsack, traveling salesperson, and assembly line balancing problems. It is shown that this model can provide an alternative to the preference order models proposed for these problems. Counterexample to the optimality of the preference order models are presented.     

New estimates of the stability of one-dimensional plane-parallel flows of a viscous incompressible fluid

The stability of a number of one-dimensional plane-parallel steady flows of a viscous incompressible fluid is investigated analytically using the method of integral relations. The mathematical formulation is reduced to eigenvalue problems for the Orr–Sommerfeld equation. One of three versions is chosen as the boundary conditions: all the components of the velocity perturbation are equal to zero on both boundaries of the layer (in this case we have the classical Orr–Sommerfeld problem), all the components of the velocity perturbation on one of the boundaries are equal to zero and the perturbations of the shear component of the stress vector and of the normal component of the velocity are equal to zero on the other, and all the components of the velocity perturbation are equal to zero on one boundary and the other boundary should be free. The boundary conditions derived in the latter case, are characterized by the occurrence of a spectral parameter in them. For kinematic conditions the lower estimates of the critical Reynolds number – the Joseph–Yih estimates, are improved. In the remaining cases the technique of the integral-relations method is developed, leading to new estimates of the stability. Analogs of Squire's theorem are derived for the boundary conditions of all the types mentioned above. Upper estimates of the increment of the increase in perturbations in eigenvalue problems for the Rayleigh equation with two types of boundary conditions are given.     

Invariant-point theorems and existence of solutions to optimization-related problems

To consider existence of solutions to various optimization-related problems, we first develop some equivalent versions of invariant-point theorems. Next, they are employed to derive sufficient conditions for the solution existence for two general models of variational relation and inclusion problems. We also prove the equivalence of these conditions with the above-mentioned invariant-point theorems. In applications, we include consequences of these results to a wide range of particular cases, from relatively general inclusion problems to classical results as Ekeland’s variational principle, and practical situations like traffic networks and non-cooperative games, to illustrate application possibilities of our general results. Many examples are provided to explain advantages of the obtained results and also to motivate in detail our problem settings.     

Three nearly scaling-invariant versions of an exterior point algorithm for linear programming

In this paper, we describe three versions of a primal exterior point Simplex type algorithm for solving linear programming problems. Also, these algorithms are not affected mainly by scaling techniques. We compare their practical effectiveness versus the revised primal Simplex algorithm (our implementation) and the MATLAB’s implementations of Simplex and Interior Point Method. A computational study on randomly generated sparse linear programs is presented to establish the practical value of the proposed versions. The results are very encouraging and verify the superiority of the exterior point versions over the other algorithms either using scaling techniques or not.     

Max Flow and Min Cut with bounded-length paths: complexity, algorithms, and approximation

We consider the “flow on paths” versions of Max Flow and Min Cut when we restrict to paths having at most B arcs, and for versions where we allow fractional solutions or require integral solutions. We show that the continuous versions are polynomial even if B is part of the input, but that the integral versions are polynomial only when B ≤ 3. However, when B ≤ 3 we show how to solve the problems using ordinary Max Flow/Min Cut. We also give tight bounds on the integrality gaps between the integral and continuous objective values for both problems, and between the continuous objective values for the bounded-length paths version and the version allowing all paths. We give a primal–dual approximation algorithm for both problems whose approximation ratio attains the integrality gap, thereby showing that it is the best possible primal–dual approximation algorithm.     

Orthogonal segment stabbing

We study a class of geometric stabbing/covering problems for sets of line segments, rays and lines in the plane. While we demonstrate that the problems on sets of horizontal/vertical line segments are NP-complete, we show that versions involving (parallel) rays or lines are polynomially solvable.     

Analytical and numerical investigation of the spectra of three-point difference operators

The properties of the spectra of discrete spatially one-dimensional problems of convection — diffusion type with constant coefficients and nonstandard boundary conditions are examined in the framework of stability of explicit algorithms for time-dependent problems of mathematical physics. An analytical method is proposed for finding isolated limit points of the operator spectrum. Limit points are determined for the difference transport equation with different versions of nonreflecting boundary conditions and for an approximation of the heat conduction equation on a grid with condensation near the boundary. Stability and other properties of the spectrum are also established numerically. __________ Translated from Prikladnaya Matematika i Informatika, No. 27, pp. 25–45, 2007.     

The quasistationary approximation in the problem of the motion of an isolated volume of a viscous incompressible capillary liquid

The equations of the quasistationary approximation in the problem of the motion of an isolated volume of a viscous incompressible capillary liquid are derived from the exact equations using an expansion in a small quasistationary parameter, which is equal to the ratio of the Stokes time to the capillary time. The problem contains yet another dimensionless parameter, which is proportional to the modulus of the conserved angular momentum of the liquid volume, which is also assumed to be small. Depending on the relation between these parameters, three versions of the limiting problem are obtained: the traditional version and two new versions. Asymptotic solutions of the problems which arise when the quasistationary parameter tends to zero are constructed.     

Conditions for the solvability of a system of integral equations by quadratures

By reduction to Goursat problems, we obtain various versions of conditions ensuring that the solution of the system in question can be constructed in closed form.     

Set-valued equilibrium problems with applications to Browder variational inclusions and to fixed point theory

In this paper, we deal with set-valued equilibrium problems under mild conditions of continuity and convexity on subsets recently introduced in the literature. We obtain that neither semicontinuity nor convexity are needed on the whole domain when solving set-valued and single-valued equilibrium problems. As applications, we derive some existence results for Browder variational inclusions, and we extend the well-known Berge maximum theorem in order to obtain two versions of Kakutani and Schauder fixed point theorems.     

On the optimal control of systems governed by nonlinear volterra equations

Existence theorems are stated and proved for optimal control problems monitored by a nonlinear Volterra-type integral equation. Growth conditions are taken into consideration which ensure the needed compactness on the set of trajectories and entail the existence of the usual optimal solutions for the given problem. Weak or approximate solutions are taken into consideration in a subsequent paper.The author would like to express his appreciation to Professor L. Cesari and Professor M. B. Suryanarayana for many helpful conversations and suggestions for the improvement of earlier versions of this paper.     

On the stability of characterization of the normal distribution by the properties of linear forms

If the assumptions of the characterization theorem are fulfilled not exactly but only approximately, then can we state that the conclusion of this characterization is also fulfilled approximately? Theorems in which this kind of problems are considered are called stability theorems or the stability of characterizations. The problems of the stability of characterization of the normal distribution by means of identically distributed linear form and monomial are considered in a uniform metric. The moment and symmetry conditions are considerably weaker in comparison to previously published versions of the theorem. The choice of a uniform metric appears to be very natural in the framework of Zolotarev’s methodology advising to investigate stability.     

Determinant Forms for Extended Heat Functions and Expansions of Solutions of Associated Cauchy Problems

We briefly review series solutions of differential equations problems of the second order that lead to coefficients expressed in terms of determinants. Derivative type formulas involving a generating function with several parameters are developed for these determinant coefficients in first order problems. These permit constructing determinant forms for the heat polynomials and their Appell transforms. Hadamard's theorem for bounding determinants and conical regions are used to deduce simplified versions of expansion theorems involving these polynomials and associated Appell transforms. Extended versions of the heat equation are also considered.