IEICE SEARCH SYSTEM

Keyword : approximation algorithm

An Approximation Algorithm for the Maximum Induced Matching Problem on C₅-Free Regular Graphs Yuichi ASAHIRO Guohui LIN Zhilong LIU Eiji MIYANO
Publication: Publication Date: 2019/09/01 Vol. E102-A No. 9 ; pp. 1142-1149 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Optimization Keyword: induced matching problem, C₅-free regular graph, approximation algorithm,
	Summary \| Full Text:PDF(1.4MB)

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-cover, approximation algorithm, upper 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: tree, maximum partition problem, supply, demand, edge-capacity, approximation 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 provisioning, network virtualization, quality of service, service composition, approximation 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 tree, QoS routing, nonlinear combination, heuristic, approximation 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 service, backbone network, optimization problem, NP-complete, approximation 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 problem, approximation algorithm, rooted 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 algorithm, graph algorithm, routing problem, network 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 problem, approximation algorithm, derandomization, pessimistic 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 compression, approximation algorithm, minimum 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 pricing, approximation algorithm, pseudodegree, valuation 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 algorithm, facility location problem, graph algorithm, multicast routing problem, network optimization, tree 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 algorithm, edge-connectivity, degree specification, graph algorithm, metric, network design, TSP,
	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 Circuit, Euler circuit, graph theory, contiguous cost, NP-complete, approximation 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 algorithm, vertex cover, perfect matching, MAX-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 scheduling, timetabling, approximation algorithm, dependent 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 problem, NP-hard, approximation algorithm, approximability, connected 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 system, certificate dispersal, approximation algorithm, NP-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 algorithm, graph algorithm, partition, subtree cover problem, traveling 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: scheduling, NP-completeness, approximation 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 algorithm, approximation algorithm, vertex-connectivity, MA orderings, minimum 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 algorithm, approximation algorithm, matching, planar graph, separator,
	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 algorithm, combinatorial optimization, matrix rounding, network 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: CAP, approximation algorithm, benchmark, NP-hard, cellular 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: agent, approximation algorithm, tasks, assignment, inapproximability,
	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 problem, approximation algorithm, connectivity, graph, hypergraph,
	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 data, class extraction, approximation 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 graph, vertex-connectivity, approximation algorithm, spanning 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 scheduling, approximation algorithm, meta-heuristic, new 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 problems, geometric optimization, approximation algorithm, PTAS, traveling salesman, Steiner 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 problem, approximation 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 warping, dynamic programming, approximation 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 management, CMIS, scope, approximation 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 tree, pattern recognition, optimization, approximation algorithm, statistical decision problem, source coding, polynomial time algorithm,
	Summary \| Full Text:PDF(716.5KB)