RUS  ENG
Full version
JOURNALS // Avtomatika i Telemekhanika // Archive

Avtomat. i Telemekh., 1982 Issue 8, Pages 120–125 (Mi at5598)

Automated control systems

On computing complexity of the problem of search for a set on options in exchange of indivisible resources

M. B. Katsnel'son, V. M. Temkin

Moscow

Abstract: The paper is concerned with search for an optimal set of options in exchange of indivisible resources which is a problem of optimal integer circulation in a network with gain in the arcs. The problem is shown to belong to the class of $NP$-difficult combinatorial problems. A procedure of reducing this problem to the well-known traveling salesman problem is described.

UDC: 65.01:519.152


Received: 03.04.1981


 English version:
Automation and Remote Control, 1982, 43:8, 1073–1077

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024