Search academic texts

Information × Registration Number 0299U000366, 0196U008670 , R & D reports Title The research on creating the effective PDC-algorithms task for intractable combinatorial problems and new information technologies of their solution creating. popup.stage_title Head Pavlov Oleksandr Anatolijovych, Registration Date 01-03-1999 Organization National Technscal University of Ukraine "Kiev Polytechnic Institute". popup.description2 The object of research are intractable problems of combinatorial optimization. The purpose of work is the intractable problems of combinatorial optimization research and effective exact algorithms of their decision (PDC-algorithms) development. In the basis a new direction development in the theory of combinatorial optimization is fixed, which results in combinatorial problems determination from an class of intractable problems. The modified algorithm for the solution of a "Maximum In-dependent Set"(MIS) problem is developed, which uses a principle of sequential designing of variants, methods of cutting off and paralleling of calculations at realization of its PDC-algorithm polinomial realization. Conditions of MIS problem PDC-algorithm polinomial realization application are deduced. The analysis of modeling and research results for the MIS problem PDC-algorithm polinomial realization statistical efficiency is carried out. Its efficiency for some intractable problems of combinatorial optimization is an alized. Conditions of PDC-algorithm polinomial realization for "The minimization of total weighted completion time with the precedence relation given as oriented acyclic graph" (MWC) problem are obtained. The original approximate algorithm for NP-hard MWC problem solution is developed. The package of applied programs is developed and results of statistical researches of developed algorithms are indicated. The area of using: inside an automated working place for management personnel at all levels of enterprise's CAD/CAM system hierarchy. Product Description popup.authors popup.nrat_date 2020-04-03 Close