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 packingbounded terminal nodesapproximation 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 coversminimum weight vertex cover problemapproximation algorithmscomputing 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 optimizationrouting and schedulingindustrial robotsapproximation algorithmsmetric 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 biologyRNA secondary structure predictionapproximation 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 algorithmsfault-tolerant routingdisjoint pathsLagrangian 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 problemincomplete liststiesapproximation algorithmslocal 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: 
graphsaugmentation problemsedge-connectivityapproximation 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 coloringapproximation algorithmsNP-hardmaximum 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 algorithmsAPX-completemaximum weightlinear 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 SATapproximation algorithmssemidefinite 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 functionset coverapproximation algorithmsgreedy 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: 
schedulingpriority-listsapproximation algorithmstimed 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 netsschedulingapproximation algorithmstime complexityNP-hardness
 Summary | Full Text:PDF(1.1MB)