Browse

단일 추가제약을 갖는 조합최적화문제를 위한 실용적 완화해법의 계산시간 분석
A Complexity Analysis of a "pragmatic" relaxation method for the combinatorial optimization with a side constraint

DC Field Value Language
dc.contributor.author홍성필-
dc.date.accessioned2009-07-10T06:37:36Z-
dc.date.available2009-07-10T06:37:36Z-
dc.date.issued2000-
dc.identifier.citation한국경영과학회지, 제25권, 제1호(2000). pp. 27-36en
dc.identifier.issn1225-1119-
dc.identifier.urihttp://hdl.handle.net/10371/5338-
dc.identifier.urihttp://uci.or.kr/G300-j12251119.v25n1p27-
dc.description.abstractWe perform a computational complexity analysis of a heuristic algorithm proposed in the literature for the combinatorial optimization problems extended with a single side-constraint. This algorithm, although such a view was not given in the original work, is a disguised version of an optimal Lagrangian dual solution technique. It also has been observed to be a very efficient heuristic producing near-optimal solutions for the primal problems in some experiments. Especially, the number of iterations grows sublinearly in terms of the network node size so that the heuristic seems to be particularly suitable for the application such as routing with semi-real time requirements. The goal of this paper is to establish a polynomial worst-case complexity of the algorithm in particular, the obtained complexity bound supports the sublinear growth of the required iterations.en
dc.description.sponsorship이 논문은 1999년도 한국학술진흥재단의 연구비에 의하여 연구되었음(KRF-99-E00125).en
dc.language.isoko-
dc.publisher한국경영과학회 = The Korean Operations Research and Management Science Societyen
dc.title단일 추가제약을 갖는 조합최적화문제를 위한 실용적 완화해법의 계산시간 분석en
dc.title.alternativeA Complexity Analysis of a "pragmatic" relaxation method for the combinatorial optimization with a side constrainten
dc.typeArticleen
dc.contributor.AlternativeAuthorHong, Sung-Pil-
Appears in Collections:
College of Engineering/Engineering Practice School (공과대학/대학원)Dept. of Industrial Engineering (산업공학과)Journal Papers (저널논문_산업공학과)
Files in This Item:
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse