Linear time algorithms for the weighted tailored 2-partition problem and the weighted 2-center problem under l∞-distance

M. T. Ko; Yu-Tai Ching

doi:10.1016/0166-218X(92)90009-Y

Linear time algorithms for the weighted tailored 2-partition problem and the weighted 2-center problem under l_∞-distance

M. T. Ko^*, Yu-Tai Ching

^*Corresponding author for this work

Department of Computer Science

Research output: Contribution to journal › Article

4 Scopus citations

Abstract

In this paper, the weighted tailored 2-partition problem and the weighted 2-center problem under l_∞-distance are considered. An O(2^d-1·d·n) algorithm to solve the weighted tailored 2-partition problem and an O(d²·n + d²·log*d) time algorithm to solve the weighted 2-center problem in the d-dimensional case are presented.

Original language	English
Pages (from-to)	397-410
Number of pages	14
Journal	Discrete Applied Mathematics
Volume	40
Issue number	3
DOIs	https://doi.org/10.1016/0166-218X(92)90009-Y
State	Published - 14 Dec 1992

Access to Document

10.1016/0166-218X(92)90009-Y

Link to publication in Scopus

Fingerprint Dive into the research topics of 'Linear time algorithms for the weighted tailored 2-partition problem and the weighted 2-center problem under l<sub>∞</sub>-distance'. Together they form a unique fingerprint.

Cite this

Ko, M. T., & Ching, Y-T. (1992). Linear time algorithms for the weighted tailored 2-partition problem and the weighted 2-center problem under l_∞-distance. Discrete Applied Mathematics, 40(3), 397-410. https://doi.org/10.1016/0166-218X(92)90009-Y

@article{d794663b8464477eb5e1f861e3730d25,

title = "Linear time algorithms for the weighted tailored 2-partition problem and the weighted 2-center problem under l∞-distance",

abstract = "In this paper, the weighted tailored 2-partition problem and the weighted 2-center problem under l∞-distance are considered. An O(2d-1·d·n) algorithm to solve the weighted tailored 2-partition problem and an O(d2·n + d2·log*d) time algorithm to solve the weighted 2-center problem in the d-dimensional case are presented.",

author = "Ko, {M. T.} and Yu-Tai Ching",

year = "1992",

month = dec,

day = "14",

doi = "10.1016/0166-218X(92)90009-Y",

language = "English",

volume = "40",

pages = "397--410",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - Linear time algorithms for the weighted tailored 2-partition problem and the weighted 2-center problem under l∞-distance

AU - Ko, M. T.

AU - Ching, Yu-Tai

PY - 1992/12/14

Y1 - 1992/12/14

N2 - In this paper, the weighted tailored 2-partition problem and the weighted 2-center problem under l∞-distance are considered. An O(2d-1·d·n) algorithm to solve the weighted tailored 2-partition problem and an O(d2·n + d2·log*d) time algorithm to solve the weighted 2-center problem in the d-dimensional case are presented.

AB - In this paper, the weighted tailored 2-partition problem and the weighted 2-center problem under l∞-distance are considered. An O(2d-1·d·n) algorithm to solve the weighted tailored 2-partition problem and an O(d2·n + d2·log*d) time algorithm to solve the weighted 2-center problem in the d-dimensional case are presented.

UR - http://www.scopus.com/inward/record.url?scp=38249009511&partnerID=8YFLogxK

U2 - 10.1016/0166-218X(92)90009-Y

DO - 10.1016/0166-218X(92)90009-Y

M3 - Article

AN - SCOPUS:38249009511

VL - 40

SP - 397

EP - 410

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 3

ER -