Publication IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer SciencesVol.E74-ANo.4pp.665-668 Publication Date: 1991/04/25 Online ISSN: DOI: Print ISSN: 0916-8508 Type of Manuscript: Special Section PAPER (Special Issue on Discrete Mathematics and Its Applications) Category: Keyword:
Full Text: PDF>>
Summary: This paper gives an O(n log n)-time algorithm for the following problem: min Σni=1|xi-ai| s.t.x1x2xn where ai(i=1, , n) are given constants and xi(i=1, , n) are variables. There has been given an O(n2)-time incremental algorithm, and we improve it by using the heap as a data structure and modify the incremental algorithm partly. This problem is a kind of the geometric fitting problem between two corresponding sets of points on a line which is related to some VLSI layout design problem.