On the hardness of approximate multivariate integration

Ioannis Koutis

doi:10.1007/978-3-540-45198-3_11

On the hardness of approximate multivariate integration

Ioannis Koutis

Research output: Chapter in Book/Report/Conference proceeding › Chapter

1 Scopus citations

Abstract

We show that it is NP-hard to 2^nk-approximate the integral of a positive, smooth, polynomial-time computable n-variate function, for any fixed integer k.

Original language	English (US)
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Sanjeev Asora, Amit Sahai, Klaus Jansen, Jose D.P. Rolim
Publisher	Springer Verlag
Pages	122-128
Number of pages	7
ISBN (Print)	3540407707, 9783540407706
DOIs	https://doi.org/10.1007/978-3-540-45198-3_11
State	Published - 2003
Externally published	Yes

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2764
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-45198-3_11

Cite this

Koutis, I. (2003). On the hardness of approximate multivariate integration. In S. Asora, A. Sahai, K. Jansen, & J. D. P. Rolim (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 122-128). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2764). Springer Verlag. https://doi.org/10.1007/978-3-540-45198-3_11

Koutis, Ioannis. / On the hardness of approximate multivariate integration. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Sanjeev Asora ; Amit Sahai ; Klaus Jansen ; Jose D.P. Rolim. Springer Verlag, 2003. pp. 122-128 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{1611f736fc7c43ebac44d4a7f40c8080,

title = "On the hardness of approximate multivariate integration",

abstract = "We show that it is NP-hard to 2nk-approximate the integral of a positive, smooth, polynomial-time computable n-variate function, for any fixed integer k.",

author = "Ioannis Koutis",

year = "2003",

doi = "10.1007/978-3-540-45198-3_11",

language = "English (US)",

isbn = "3540407707",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "122--128",

editor = "Sanjeev Asora and Amit Sahai and Klaus Jansen and Rolim, {Jose D.P.}",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

address = "Germany",

}

Koutis, I 2003, On the hardness of approximate multivariate integration. in S Asora, A Sahai, K Jansen & JDP Rolim (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2764, Springer Verlag, pp. 122-128. https://doi.org/10.1007/978-3-540-45198-3_11

On the hardness of approximate multivariate integration. / Koutis, Ioannis.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Sanjeev Asora; Amit Sahai; Klaus Jansen; Jose D.P. Rolim. Springer Verlag, 2003. p. 122-128 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2764).

Research output: Chapter in Book/Report/Conference proceeding › Chapter

TY - CHAP

T1 - On the hardness of approximate multivariate integration

AU - Koutis, Ioannis

PY - 2003

Y1 - 2003

N2 - We show that it is NP-hard to 2nk-approximate the integral of a positive, smooth, polynomial-time computable n-variate function, for any fixed integer k.

AB - We show that it is NP-hard to 2nk-approximate the integral of a positive, smooth, polynomial-time computable n-variate function, for any fixed integer k.

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

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

U2 - 10.1007/978-3-540-45198-3_11

DO - 10.1007/978-3-540-45198-3_11

M3 - Chapter

AN - SCOPUS:35248825539

SN - 3540407707

SN - 9783540407706

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 122

EP - 128

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Asora, Sanjeev

A2 - Sahai, Amit

A2 - Jansen, Klaus

A2 - Rolim, Jose D.P.

PB - Springer Verlag

ER -

Koutis I. On the hardness of approximate multivariate integration. In Asora S, Sahai A, Jansen K, Rolim JDP, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2003. p. 122-128. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-45198-3_11

On the hardness of approximate multivariate integration

Abstract

Publication series

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this