IEICE Trans

Keyword : approximation algorithms

Approximation Algorithms for Packing Element-Disjoint Steiner Trees on Bounded Terminal Nodes Daiki HOSHIKA Eiji MIYANO
Publication: IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Publication Date: 2016/06/01 Vol. E99-A No. 6 ; pp. 1059-1066 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: element-disjoint Steiner tree packing, bounded terminal nodes, approximation algorithms,
	Summary \| Full Text:PDF(756.5KB)

Computing-Based Performance Analysis of Approximation Algorithms for the Minimum Weight Vertex Cover Problem of Graphs Satoshi TAOKA Daisuke TAKAFUJI Toshimasa WATANABE
Publication: IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Publication Date: 2013/06/01 Vol. E96-A No. 6 ; pp. 1331-1339 Type of Manuscript: Special Section PAPER (Special Section on Circuit, System, and Computer Technologies) Category: Keyword: vertex covers, minimum weight vertex cover problem, approximation algorithms, computing experiment,
	Summary \| Full Text:PDF(1.5MB)

Better Approximation Algorithms for Grasp-and-Delivery Robot Routing Problems Aleksandar SHURBEVSKI Hiroshi NAGAMOCHI Yoshiyuki KARUNO
Publication: IEICE TRANSACTIONS on Information and Systems Publication Date: 2013/03/01 Vol. E96-D No. 3 ; pp. 450-456 Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — New Trends in Algorithms and Theory of Computation —) Category: Keyword: combinatorial optimization, routing and scheduling, industrial robots, approximation algorithms, metric traveling salesperson problem,
	Summary \| Full Text:PDF(261.4KB)

Approximation Algorithms for Optimal RNA Secondary Structures Common to Multiple Sequences Takeyuki TAMURA Tatsuya AKUTSU
Publication: IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Publication Date: 2007/05/01 Vol. E90-A No. 5 ; pp. 917-923 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: computational biology, RNA secondary structure prediction, approximation algorithms,
	Summary \| Full Text:PDF(305.3KB)

A New Approximation Algorithm for Computing 2-Restricted Disjoint Paths Chao PENG Hong SHEN
Publication: IEICE TRANSACTIONS on Information and Systems Publication Date: 2007/02/01 Vol. E90-D No. 2 ; pp. 465-472 Type of Manuscript: PAPER Category: Algorithm Theory Keyword: approximation algorithms, fault-tolerant routing, disjoint paths, Lagrangian Relaxation,
	Summary \| Full Text:PDF(311.2KB)

A -Approximation Algorithm for the Stable Marriage Problem Kazuo IWAMA Shuichi MIYAZAKI Kazuya OKAMOTO
Publication: IEICE TRANSACTIONS on Information and Systems Publication Date: 2006/08/01 Vol. E89-D No. 8 ; pp. 2380-2387 Type of Manuscript: INVITED PAPER (Special Section on Invited Papers from New Horizons in Computing) Category: Keyword: stable marriage problem, incomplete lists, ties, approximation algorithms, local search,
	Summary \| Full Text:PDF(225.3KB)

A 2-Approximation Algorithm to (k + 1)-Edge-Connect a Specified Set of Vertices in a k-Edge-Connected Graph Toshiya MASHIMA Satoshi TAOKA Toshimasa WATANABE
Publication: IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Publication Date: 2005/05/01 Vol. E88-A No. 5 ; pp. 1290-1300 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: graphs, augmentation problems, edge-connectivity, approximation algorithms,
	Summary \| Full Text:PDF(387.2KB)

On Approximation Algorithms for Coloring k-Colorable Graphs Xuzhen XIE Takao ONO Tomio HIRATA
Publication: IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Publication Date: 2003/05/01 Vol. E86-A No. 5 ; pp. 1046-1051 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: graph coloring, approximation algorithms, NP-hard, maximum degree,
	Summary \| Full Text:PDF(227.3KB)

Approximating the Maximum Weight of Linear Codes is APX-Complete Toshiya ITOH
Publication: IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Publication Date: 2000/04/25 Vol. E83-A No. 4 ; pp. 606-613 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: approximation algorithms, APX-complete, maximum weight, linear codes,
	Summary \| Full Text:PDF(332.8KB)

Approximation Algorithms for MAX SAT Tomio HIRATA Takao ONO
Publication: IEICE TRANSACTIONS on Information and Systems Publication Date: 2000/03/25 Vol. E83-D No. 3 ; pp. 488-495 Type of Manuscript: INVITED SURVEY PAPER Category: Approximate Algorithms for Combinatorial Problems Keyword: MAX SAT, approximation algorithms, semidefinite programming,
	Summary \| Full Text:PDF(353.4KB)

Approximation Algorithms for Submodular Set Cover with Applications Toshihiro FUJITO
Publication: IEICE TRANSACTIONS on Information and Systems Publication Date: 2000/03/25 Vol. E83-D No. 3 ; pp. 480-487 Type of Manuscript: INVITED SURVEY PAPER Category: Approximate Algorithms for Combinatorial Problems Keyword: submodular function, set cover, approximation algorithms, greedy heuristics,
	Summary \| Full Text:PDF(283.9KB)

Priority-List Scheduling in Timed Petri Nets Takenobu TANIDA Toshimasa WATANABE Masahiro YAMAUCHI Kinji ONAGA
Publication: IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Publication Date: 1992/10/25 Vol. E75-A No. 10 ; pp. 1394-1406 Type of Manuscript: Special Section PAPER (Special Section on Application of Petri Nets to Concurrent System Design) Category: Keyword: scheduling, priority-lists, approximation algorithms, timed Petri nets,
	Summary \| Full Text:PDF(987.1KB)

The Minimum Initial Marking Problem for Scheduling in Timed Petri Nets Toshimasa WATANABE Takenobu TANIDA Masahiro YAMAUCHI Kenji ONAGA
Publication: IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Publication Date: 1992/10/25 Vol. E75-A No. 10 ; pp. 1407-1421 Type of Manuscript: Special Section PAPER (Special Section on Application of Petri Nets to Concurrent System Design) Category: Keyword: timed Petri nets, scheduling, approximation algorithms, time complexity, NP-hardness,
	Summary \| Full Text:PDF(1.1MB)