Operations Research and Discrete Analysis

This book contains translations of papers from the second volume of the new Russian-language journal published at the Sobolev Institute of Mathematics (Sibe rian Branch of the Russian Academy of Sciences, Novosibirsk) since 1994. In 1994 the journal was titled Sibirskil Zhurnal Issledovaniya Oper atsil. Since 1995 this journal has the title Diskretny'l Analiz i Issledovanie Operatsi'l (Discrete Analysis and Operations Research). The aim of this journal is to bring together research papers in different areas of discrete mathematics and computer science. The journal DiskretnYl Analiz i Issledovanie Operatsil covers the following fields: discrete optimization synthesis and complexity discrete structures and of control systems extremal problems automata combinatorics graphs control and reliability game theory and its of discrete devices applications mathematical models and coding theory methods of decision making scheduling theory design and analysis functional systems theory of algorithms Contributions presented to the journal can be original research papers and occasional survey articles of moderate length. The journal is published in one volume of four issues per year that appear in March, June, September, and December. Each volume contains approximately 400 pages. I express my sincere gratitude to Professor S. S. Kutateladze for his help in editing the English translation.

Inhalt
On Discrete Approximations of Continuous Functions with Bounded Second Derivative.- On a Property of Perfect Binary Codes.- Edge Neighborhoods in Normal Maps.- An Upper Bound for the Length of a Snake in the n-Dimensional Unit Cube.- Operations and Isometric Embeddings of Graphs Related to the Metric Prolongation Property.- Effective Algorithms for Solving Multi-Level Plant Location Problem.- On the Complexity of Realization of Boolean Functions by Circuits over an Infinite Basis.- Dynamic Problems of Choosing Optimal Composition of a System of Technical Tools.- Lower Bounds in the Problem of Choosing an Optimal Composition of a Two-Level System of Technical Tools.- On Schedules of a Single Machine Jobs with Processing Times Nonlinear in Time.- Problems of Reconstructing Words from Their Fragments and Applications.- A Vertex Variant of the Kleitman-West Problem.- Regular Graphs Whose Every Edge Belongs to Many Triangles.- On Closed Classes in k-Valued Logic Which Contain a Homogeneous Switching function.- Strongly Essential Variables of the Functions of k- Valued Logic.- On Comparison Between the Sizes of Read-k-Times Branching Programs.- Some Optimization Problems of Scheduling the Transmission of Messages in a Local Communication Network.- The Maximum-Weight Traveling Salesman Problem in Finite-Dimensional Real Spaces.- Nonstrict Vector Summation in the Plane and Its Applications to Scheduling Problems.- Bounds for Approximate Solution of a Scheduling Problem.- On Certain Bounds for the Weight of l-Balanced Boolean Functions.- Spectral Properties of Perfect Binary (n,Z)-Codes.- Distributive Coloring of Graph Vertices.- Deciphering Threshold Functions of k- Valued Logic.