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

Avtomat. i Telemekh., 1983 Issue 8, Pages 150–155 (Mi at5202)

Automated control systems

On computing complexity of choosing exchange options with a limited number of resources

V. M. Temkin

Moscow

Abstract: Choice of an optimal set of exchange options with a limited number of indivisible resources is discussed for the a general case of equitable exchanges. In both cases the problem is proved to belong to the class of $NP$-difficult combinatorial problems. A procedure of reducing the well-known $NP$-difficult problem of vertex graph cover to this problem is described.

UDC: [002.513.5:681.31]:643


Received: 11.03.1982


 English version:
Automation and Remote Control, 1983, 44:8, 1090–1095

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024