Budget feasible mechanisms for experimental design

Thibaut Horel; Stratis Ioannidis; S. Muthukrishnan

doi:10.1007/978-3-642-54423-1_62

Budget feasible mechanisms for experimental design

Thibaut Horel, Stratis Ioannidis, S. Muthukrishnan

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

Abstract

We present a deterministic, polynomial time, budget feasible mechanism scheme, that is approximately truthful and yields a constant (≈ 12.98) factor approximation for the Experimental Design Problem (EDP). By applying previous work on budget feasible mechanisms with a submodular objective, one could only have derived either an exponential time deterministic mechanism or a randomized polynomial time mechanism. We also establish that no truthful, budget-feasible mechanism is possible within a factor 2 approximation, and show how to generalize our approach to a wide class of learning problems, beyond linear regression.

Original language	English (US)
Title of host publication	LATIN 2014
Subtitle of host publication	Theoretical Informatics - 11th Latin American Symposium, Proceedings
Publisher	Springer Verlag
Pages	719-730
Number of pages	12
ISBN (Print)	9783642544224
DOIs	https://doi.org/10.1007/978-3-642-54423-1_62
State	Published - 2014
Event	11th Latin American Theoretical Informatics Symposium, LATIN 2014 - Montevideo, Uruguay Duration: Mar 31 2014 → Apr 4 2014

Publication series

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

Conference

Conference	11th Latin American Theoretical Informatics Symposium, LATIN 2014
Country/Territory	Uruguay
City	Montevideo
Period	3/31/14 → 4/4/14

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-54423-1_62

Cite this

Horel, T., Ioannidis, S., & Muthukrishnan, S. (2014). Budget feasible mechanisms for experimental design. In LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Proceedings (pp. 719-730). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8392 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-642-54423-1_62

Budget feasible mechanisms for experimental design. / Horel, Thibaut; Ioannidis, Stratis; Muthukrishnan, S.
LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Proceedings. Springer Verlag, 2014. p. 719-730 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8392 LNCS).

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

Horel, T, Ioannidis, S & Muthukrishnan, S 2014, Budget feasible mechanisms for experimental design. in LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8392 LNCS, Springer Verlag, pp. 719-730, 11th Latin American Theoretical Informatics Symposium, LATIN 2014, Montevideo, Uruguay, 3/31/14. https://doi.org/10.1007/978-3-642-54423-1_62

Horel T, Ioannidis S, Muthukrishnan S. Budget feasible mechanisms for experimental design. In LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Proceedings. Springer Verlag. 2014. p. 719-730. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-54423-1_62

@inproceedings{83c8415735fa4800b7e8eb4992b3a3ed,

title = "Budget feasible mechanisms for experimental design",

abstract = "We present a deterministic, polynomial time, budget feasible mechanism scheme, that is approximately truthful and yields a constant (≈ 12.98) factor approximation for the Experimental Design Problem (EDP). By applying previous work on budget feasible mechanisms with a submodular objective, one could only have derived either an exponential time deterministic mechanism or a randomized polynomial time mechanism. We also establish that no truthful, budget-feasible mechanism is possible within a factor 2 approximation, and show how to generalize our approach to a wide class of learning problems, beyond linear regression.",

author = "Thibaut Horel and Stratis Ioannidis and S. Muthukrishnan",

year = "2014",

doi = "10.1007/978-3-642-54423-1_62",

language = "English (US)",

isbn = "9783642544224",

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

publisher = "Springer Verlag",

pages = "719--730",

booktitle = "LATIN 2014",

note = "11th Latin American Theoretical Informatics Symposium, LATIN 2014 ; Conference date: 31-03-2014 Through 04-04-2014",

}

TY - GEN

T1 - Budget feasible mechanisms for experimental design

AU - Horel, Thibaut

AU - Ioannidis, Stratis

AU - Muthukrishnan, S.

PY - 2014

Y1 - 2014

N2 - We present a deterministic, polynomial time, budget feasible mechanism scheme, that is approximately truthful and yields a constant (≈ 12.98) factor approximation for the Experimental Design Problem (EDP). By applying previous work on budget feasible mechanisms with a submodular objective, one could only have derived either an exponential time deterministic mechanism or a randomized polynomial time mechanism. We also establish that no truthful, budget-feasible mechanism is possible within a factor 2 approximation, and show how to generalize our approach to a wide class of learning problems, beyond linear regression.

AB - We present a deterministic, polynomial time, budget feasible mechanism scheme, that is approximately truthful and yields a constant (≈ 12.98) factor approximation for the Experimental Design Problem (EDP). By applying previous work on budget feasible mechanisms with a submodular objective, one could only have derived either an exponential time deterministic mechanism or a randomized polynomial time mechanism. We also establish that no truthful, budget-feasible mechanism is possible within a factor 2 approximation, and show how to generalize our approach to a wide class of learning problems, beyond linear regression.

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

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

U2 - 10.1007/978-3-642-54423-1_62

DO - 10.1007/978-3-642-54423-1_62

M3 - Conference contribution

AN - SCOPUS:84899921103

SN - 9783642544224

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

SP - 719

EP - 730

BT - LATIN 2014

PB - Springer Verlag

T2 - 11th Latin American Theoretical Informatics Symposium, LATIN 2014

Y2 - 31 March 2014 through 4 April 2014

ER -

Budget feasible mechanisms for experimental design

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this