General Information
    • ISSN: 1793-8201 (Print), 2972-4511 (Online)
    • Abbreviated Title: Int. J. Comput. Theory Eng.
    • Frequency: Quarterly
    • DOI: 10.7763/IJCTE
    • Editor-in-Chief: Prof. Mehmet Sahinoglu
    • Associate Editor-in-Chief: Assoc. Prof. Alberto Arteta, Assoc. Prof. Engin Maşazade
    • Managing Editor: Ms. Mia Hu
    • Abstracting/Indexing: Scopus (Since 2022), INSPEC (IET), CNKI,  Google Scholar, EBSCO, etc.
    • Average Days from Submission to Acceptance: 192 days
    • E-mail: ijcte@iacsitp.com
    • Journal Metrics:

Editor-in-chief
Prof. Mehmet Sahinoglu
Computer Science Department, Troy University, USA
I'm happy to take on the position of editor in chief of IJCTE. We encourage authors to submit papers concerning any branch of computer theory and engineering.

IJCTE 2016 Vol.8(2): 145-149 ISSN: 1793-8201
DOI: 10.7763/IJCTE.2016.V8.1034

A Simple Approximation Algorithm for the Modified Bottleneck Assignment Problem in Vector Case

Yuusaku Kamura and Mario Nakamori

Abstract—We deal with the modified bottleneck assignment problem in vector case. The problem is to find the complete matching between two vector sets that minimizes the maximum sum of vectors' elements. In scalar case, there is a simple polynomial time algorithm that uses the order of elements' value. We extend this problem to the 2 dimensional vector case and propose a simple approximation algorithm for it. We show the effectiveness of our algorithm by numerical experiments.

Index Terms—Approximation algorithm, assignment problem, balanced assignment problem.

Y. Kamura is with Academic Planning Center, Hitotsubashi University, Kunitachi, Tokyo 186-8601, Japan (e-mail: b101440u@r.hit-u.ac.jp).
M. Nakamori was with Tokyo University of Agriculture and Technology, Koganei, Tokyo 184-8588, Japan. He is now with MOC Co, Ltd. Japan (e-mail: nakamori@cc.tuat.ac.jp).

[PDF]

Cite:Yuusaku Kamura and Mario Nakamori, "A Simple Approximation Algorithm for the Modified Bottleneck Assignment Problem in Vector Case," International Journal of Computer Theory and Engineering vol. 8, no. 2, pp. 145-149, 2016.


Copyright © 2008-2024. International Association of Computer Science and Information Technology. All rights reserved.