Keyword : approximation algorithm


Worst Case Analysis of Approximation Algorithm of Abrams et al. for the Set k-Cover Problem
Satoshi FUJITA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2014/03/01
Vol. E97-D  No. 3 ; pp. 399-405
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science —New Trends in Theory of Computation and Algorithm—)
Category: Optimizing Algorithms, Parallel and Distributed Computing
Keyword: 
Set k-coverapproximation algorithmupper bound on the performance ratio
 Summary | Full Text:PDF(355.4KB)

Partitioning Trees with Supply, Demand and Edge-Capacity
Masaki KAWABATA Takao NISHIZEKI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2013/06/01
Vol. E96-A  No. 6 ; pp. 1036-1043
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
treemaximum partition problemsupplydemandedge-capacityapproximation algorithm
 Summary | Full Text:PDF(1.2MB)

Modeling and Algorithms for QoS-Aware Service Composition in Virtualization-Based Cloud Computing
Jun HUANG Yanbing LIU Ruozhou YU Qiang DUAN Yoshiaki TANAKA 
Publication:   IEICE TRANSACTIONS on Communications
Publication Date: 2013/01/01
Vol. E96-B  No. 1 ; pp. 10-19
Type of Manuscript:  Special Section PAPER (Special Section on Network Virtualization, and Fusion Platform of Computing and Networking)
Category: 
Keyword: 
cloud service provisioningnetwork virtualizationquality of serviceservice compositionapproximation algorithm
 Summary | Full Text:PDF(1.1MB)

On Approximating a Multicast Routing Tree with Multiple Quality-of-Service Constraints
Jun HUANG Yoshiaki TANAKA Yan MA 
Publication:   IEICE TRANSACTIONS on Communications
Publication Date: 2012/06/01
Vol. E95-B  No. 6 ; pp. 2005-2012
Type of Manuscript:  PAPER
Category: Network
Keyword: 
multicast treeQoS routingnonlinear combinationheuristicapproximation algorithm
 Summary | Full Text:PDF(1.1MB)

Network Design Methods for Minimizing Number of Links Added to a Network to Alleviate Performance Degradation Following a Link Failure
Nozomu KATAYAMA Takeshi FUJIMURA Hiroyoshi MIWA Noriaki KAMIYAMA Haruhisa HASEGAWA Hideaki YOSHINO 
Publication:   IEICE TRANSACTIONS on Communications
Publication Date: 2011/06/01
Vol. E94-B  No. 6 ; pp. 1630-1639
Type of Manuscript:  PAPER
Category: Fundamental Theories for Communications
Keyword: 
quality of servicebackbone networkoptimization problemNP-completeapproximation algorithm
 Summary | Full Text:PDF(2.6MB)

Improved Approximation Algorithms for Firefighter Problem on Trees
Yutaka IWAIKAWA Naoyuki KAMIYAMA Tomomi MATSUI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2011/02/01
Vol. E94-D  No. 2 ; pp. 196-199
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science -- Mathematical Foundations and Applications of Algorithms and Computer Science --)
Category: 
Keyword: 
firefighter problemapproximation algorithmrooted tree
 Summary | Full Text:PDF(184.9KB)

Approximation to the Minimum Cost Edge Installation Problem
Ehab MORSY Hiroshi NAGAMOCHI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2010/04/01
Vol. E93-A  No. 4 ; pp. 778-786
Type of Manuscript:  PAPER
Category: Algorithms and Data Structures
Keyword: 
approximation algorithmgraph algorithmrouting problemnetwork optimization
 Summary | Full Text:PDF(250KB)

A Deterministic Approximation Algorithm for Maximum 2-Path Packing
Ruka TANAHASHI Zhi-Zhong CHEN 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2010/02/01
Vol. E93-D  No. 2 ; pp. 241-249
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science)
Category: 
Keyword: 
2-path packing problemapproximation algorithmderandomizationpessimistic estimator method
 Summary | Full Text:PDF(320KB)

A Space-Saving Approximation Algorithm for Grammar-Based Compression
Hiroshi SAKAMOTO Shirou MARUYAMA Takuya KIDA Shinichi SHIMOZONO 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2009/02/01
Vol. E92-D  No. 2 ; pp. 158-165
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science)
Category: 
Keyword: 
grammar-based compressionapproximation algorithmminimum CFG problem
 Summary | Full Text:PDF(667.1KB)

Improved Approximation Algorithms for Item Pricing with Bounded Degree and Valuation
Ryoso HAMANE Toshiya ITOH 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2008/02/01
Vol. E91-D  No. 2 ; pp. 187-199
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science)
Category: Approximation Algorithms
Keyword: 
item pricingapproximation algorithmpseudodegreevaluation ratio
 Summary | Full Text:PDF(302.1KB)

Approximation Algorithms for Multicast Routings in a Network with Multi-Sources
Ehab MOSRY Hiroshi NAGAMOCHI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2007/05/01
Vol. E90-A  No. 5 ; pp. 900-906
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
approximation algorithmfacility location problemgraph algorithmmulticast routing problemnetwork optimizationtree cover
 Summary | Full Text:PDF(195.1KB)

Approximating a Generalization of Metric TSP
Takuro FUKUNAGA Hiroshi NAGAMOCHI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2007/02/01
Vol. E90-D  No. 2 ; pp. 432-439
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science)
Category: Graph Algorithms
Keyword: 
approximation algorithmedge-connectivitydegree specificationgraph algorithmmetricnetwork designTSP
 Summary | Full Text:PDF(376.3KB)

Optimal Euler Circuit of Maximum Contiguous Cost
Yu QIAO Makoto YASUHARA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2007/01/01
Vol. E90-A  No. 1 ; pp. 274-280
Type of Manuscript:  PAPER
Category: Graphs and Networks
Keyword: 
Optimal Euler CircuitEuler circuitgraph theorycontiguous costNP-completeapproximation algorithm
 Summary | Full Text:PDF(250.7KB)

Approximated Vertex Cover for Graphs with Perfect Matchings
Tomokazu IMAMURA Kazuo IWAMA Tatsuie TSUKIJI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2006/08/01
Vol. E89-D  No. 8 ; pp. 2405-2410
Type of Manuscript:  INVITED PAPER (Special Section on Invited Papers from New Horizons in Computing)
Category: 
Keyword: 
approximation algorithmvertex coverperfect matchingMAX-2SAT
 Summary | Full Text:PDF(214.4KB)

Dependent Randomized Rounding to the Home-Away Assignment Problem in Sports Scheduling
Ayami SUZUKA Ryuhei MIYASHIRO Akiko YOSHISE Tomomi MATSUI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2006/05/01
Vol. E89-A  No. 5 ; pp. 1407-1416
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
sports schedulingtimetablingapproximation algorithmdependent randomized rounding
 Summary | Full Text:PDF(252.8KB)

Inapproximability of the Edge-Contraction Problem
Hideaki OTSUKI Tomio HIRATA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2006/05/01
Vol. E89-A  No. 5 ; pp. 1425-1427
Type of Manuscript:  Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
edge-contraction problemNP-hardapproximation algorithmapproximabilityconnected vertex cover problem
 Summary | Full Text:PDF(103.1KB)

An Approximation Algorithm for Minimum Certificate Dispersal Problems
Hua ZHENG Shingo OMURA Koichi WADA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2006/02/01
Vol. E89-A  No. 2 ; pp. 551-558
Type of Manuscript:  PAPER
Category: Graphs and Networks
Keyword: 
public-key based security systemcertificate dispersalapproximation algorithmNP-Complete
 Summary | Full Text:PDF(191.8KB)

Approximating the Minmax Rooted-Subtree Cover Problem
Hiroshi NAGAMOCHI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2005/05/01
Vol. E88-A  No. 5 ; pp. 1335-1338
Type of Manuscript:  PAPER
Category: Graphs and Networks
Keyword: 
approximation algorithmgraph algorithmpartitionsubtree cover problemtraveling salesman problem
 Summary | Full Text:PDF(100.8KB)

A Note on the Complexity of Scheduling for Precedence Constrained Messages in Distributed Systems
Koji GODA Toshinori YAMADA Shuichi UENO 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2005/04/01
Vol. E88-A  No. 4 ; pp. 1090-1092
Type of Manuscript:  LETTER
Category: Algorithms and Data Structures
Keyword: 
schedulingNP-completenessapproximation algorithm
 Summary | Full Text:PDF(69.6KB)

On 2-Approximation to the Vertex-Connectivity in Graphs
Hiroshi NAGAMOCHI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2005/01/01
Vol. E88-D  No. 1 ; pp. 12-16
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science)
Category: 
Keyword: 
graph algorithmapproximation algorithmvertex-connectivityMA orderingsminimum degree
 Summary | Full Text:PDF(128.7KB)

Approximability of the Minimum Maximal Matching Problem in Planar Graphs
Hiroshi NAGAMOCHI Yukihiro NISHIDA Toshihide IBARAKI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2003/12/01
Vol. E86-A  No. 12 ; pp. 3251-3258
Type of Manuscript:  PAPER
Category: Graphs and Networks
Keyword: 
graph algorithmapproximation algorithmmatchingplanar graphseparator
 Summary | Full Text:PDF(259.3KB)

Digital Halftoning: Algorithm Engineering Challenges
Tetsuo ASANO 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2003/02/01
Vol. E86-D  No. 2 ; pp. 159-178
Type of Manuscript:  INVITED SURVEY PAPER
Category: 
Keyword: 
approximation algorithmcombinatorial optimizationmatrix roundingnetwork flow
 Summary | Full Text:PDF(4.7MB)

A Quasi-Solution State Evolution Algorithm for Channel Assignment Problems in Cellular Networks
Nobuo FUNABIKI Toru NAKANISHI Tokumi YOKOHIRA Shigeto TAJIMA Teruo HIGASHINO 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2002/05/01
Vol. E85-A  No. 5 ; pp. 977-987
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
CAPapproximation algorithmbenchmarkNP-hardcellular network
 Summary | Full Text:PDF(623.9KB)

An Approximation Algorithm for the Task-Coalition Assignment Problem
Yoshihiro MURATA Yasunori ISHIHARA Minoru ITO 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2002/04/01
Vol. E85-D  No. 4 ; pp. 685-693
Type of Manuscript:  PAPER
Category: Algorithms
Keyword: 
agentapproximation algorithmtasksassignmentinapproximability
 Summary | Full Text:PDF(482KB)

A Note on Approximating the Survivable Network Design Problem in Hypergraphs
Liang ZHAO Hiroshi NAGAMOCHI Toshihide IBARAKI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2002/02/01
Vol. E85-D  No. 2 ; pp. 322-326
Type of Manuscript:  Special Section PAPER (Special Issue on Selected Papers from LA Symposium)
Category: 
Keyword: 
survivable network design problemapproximation algorithmconnectivitygraphhypergraph
 Summary | Full Text:PDF(368.9KB)

Extracting Typical Classes and a Database Schema from Semistructured Data
Nobutaka SUZUKI Yoichirou SATO Michiyoshi HAYASE 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2001/01/01
Vol. E84-D  No. 1 ; pp. 100-112
Type of Manuscript:  PAPER
Category: Databases
Keyword: 
semistructured dataclass extractionapproximation algorithm
 Summary | Full Text:PDF(613.6KB)

A 7/3-Approximation for the Minimum Weight 3-Connected Spanning Subgraph Problem
Hiroshi NAGAMOCHI Katsuhiro SEKI Toshihide IBARAKI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2000/04/25
Vol. E83-A  No. 4 ; pp. 687-691
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
undirected graphvertex-connectivityapproximation algorithmspanning subgraph
 Summary | Full Text:PDF(392.2KB)

Approximation Algorithms for Scheduling Problems
Hiroaki ISHII Minoru TADA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2000/03/25
Vol. E83-D  No. 3 ; pp. 496-502
Type of Manuscript:  INVITED SURVEY PAPER
Category: Approximate Algorithms for Combinatorial Problems
Keyword: 
multi-objective schedulingapproximation algorithmmeta-heuristicnew search method
 Summary | Full Text:PDF(309KB)

Approximation Algorithms for Geometric Optimization Problems
Hisao TAMAKI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2000/03/25
Vol. E83-D  No. 3 ; pp. 455-461
Type of Manuscript:  INVITED SURVEY PAPER
Category: Algorithms for Geometric Problems
Keyword: 
NP-hard optimization problemsgeometric optimizationapproximation algorithmPTAStraveling salesmanSteiner tree
 Summary | Full Text:PDF(259.1KB)

Approximation Algorithms for Multiprocessor Scheduling Problem
Satoshi FUJITA Masafumi YAMASHITA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2000/03/25
Vol. E83-D  No. 3 ; pp. 503-509
Type of Manuscript:  INVITED SURVEY PAPER
Category: Approximate Algorithms for Combinatorial Problems
Keyword: 
multiprocessor scheduling problemapproximation algorithm
 Summary | Full Text:PDF(306.7KB)

An Approximation Algorithm for Two-Dimensional Warping
Seiichi UCHIDA Hiroaki SAKOE 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2000/01/25
Vol. E83-D  No. 1 ; pp. 109-111
Type of Manuscript:  LETTER
Category: Image Processing, Image Pattern Recognition
Keyword: 
two-dimensional warpingdynamic programmingapproximation algorithm
 Summary | Full Text:PDF(552.9KB)

Approximation Algorithm for Optimal Combinations of Scopes in OSI Management Operations
Kiyohito YOSHIHARA Hiroki HORIUCHI Keizo SUGIYAMA Sadao OBANA 
Publication:   IEICE TRANSACTIONS on Communications
Publication Date: 1997/06/25
Vol. E80-B  No. 6 ; pp. 881-887
Type of Manuscript:  Special Section PAPER (Special Issue on Network Operations and Management)
Category: Protocol
Keyword: 
OSI managementCMISscopeapproximation algorithm
 Summary | Full Text:PDF(579KB)

An Approximate Algorithm for Decision Tree Design
Satoru OHTA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1992/05/25
Vol. E75-A  No. 5 ; pp. 622-630
Type of Manuscript:  PAPER
Category: Optimization Techniques
Keyword: 
decision treepattern recognitionoptimizationapproximation algorithmstatistical decision problemsource codingpolynomial time algorithm
 Summary | Full Text:PDF(716.5KB)