Problems over Information Systems

Igor Chikalov

doi:10.1007/978-3-642-22661-8_5

Problems over Information Systems

Igor Chikalov

Computer, Electrical and Mathematical Sciences and Engineering

Research output: Contribution to journal › Article › peer-review

Abstract

The problems of estimation of the minimum average time complexity of decision trees and design of efficient algorithms are complex in general case. The upper bounds described in Chap. 2.4.3 can not be applied directly due to large computational complexity of the parameter M(z). Under reasonable assumptions about the relation of P and NP, there are no polynomial time algorithms with good approximation ratio [12, 32]. One of the possible solutions is to consider particular classes of problems and improve the existing results using characteristics of the considered classes. © Springer-Verlag Berlin Heidelberg 2011.

Original language	English (US)
Pages (from-to)	79-84
Number of pages	6
Journal	Average Time Complexity of Decision Trees
Volume	21
DOIs	https://doi.org/10.1007/978-3-642-22661-8_5
State	Published - 2011

ASJC Scopus subject areas

Library and Information Sciences
General Computer Science
Information Systems and Management

Access to Document

10.1007/978-3-642-22661-8_5

Cite this

@article{296dff090f25474fbae3a8ac5130883b,

title = "Problems over Information Systems",

abstract = "The problems of estimation of the minimum average time complexity of decision trees and design of efficient algorithms are complex in general case. The upper bounds described in Chap. 2.4.3 can not be applied directly due to large computational complexity of the parameter M(z). Under reasonable assumptions about the relation of P and NP, there are no polynomial time algorithms with good approximation ratio [12, 32]. One of the possible solutions is to consider particular classes of problems and improve the existing results using characteristics of the considered classes. {\textcopyright} Springer-Verlag Berlin Heidelberg 2011.",

author = "Igor Chikalov",

note = "KAUST Repository Item: Exported on 2020-10-01",

year = "2011",

doi = "10.1007/978-3-642-22661-8_5",

language = "English (US)",

volume = "21",

pages = "79--84",

journal = "Average Time Complexity of Decision Trees",

issn = "1868-4394",

publisher = "Springer Verlag",

}

TY - JOUR

T1 - Problems over Information Systems

AU - Chikalov, Igor

N1 - KAUST Repository Item: Exported on 2020-10-01

PY - 2011

Y1 - 2011

N2 - The problems of estimation of the minimum average time complexity of decision trees and design of efficient algorithms are complex in general case. The upper bounds described in Chap. 2.4.3 can not be applied directly due to large computational complexity of the parameter M(z). Under reasonable assumptions about the relation of P and NP, there are no polynomial time algorithms with good approximation ratio [12, 32]. One of the possible solutions is to consider particular classes of problems and improve the existing results using characteristics of the considered classes. © Springer-Verlag Berlin Heidelberg 2011.

AB - The problems of estimation of the minimum average time complexity of decision trees and design of efficient algorithms are complex in general case. The upper bounds described in Chap. 2.4.3 can not be applied directly due to large computational complexity of the parameter M(z). Under reasonable assumptions about the relation of P and NP, there are no polynomial time algorithms with good approximation ratio [12, 32]. One of the possible solutions is to consider particular classes of problems and improve the existing results using characteristics of the considered classes. © Springer-Verlag Berlin Heidelberg 2011.

UR - http://hdl.handle.net/10754/561676

UR - http://link.springer.com/10.1007/978-3-642-22661-8_5

UR - http://www.scopus.com/inward/record.url?scp=84885650927&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-22661-8_5

DO - 10.1007/978-3-642-22661-8_5

M3 - Article

SN - 1868-4394

VL - 21

SP - 79

EP - 84

JO - Average Time Complexity of Decision Trees

JF - Average Time Complexity of Decision Trees

ER -

Problems over Information Systems

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this