Budget feasible mechanisms for experimental design

Thibaut Horel, Stratis Ioannidis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

19 Scopus citations

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 languageEnglish (US)
Title of host publicationLATIN 2014
Subtitle of host publicationTheoretical Informatics - 11th Latin American Symposium, Proceedings
PublisherSpringer Verlag
Pages719-730
Number of pages12
ISBN (Print)9783642544224
DOIs
StatePublished - 2014
Event11th Latin American Theoretical Informatics Symposium, LATIN 2014 - Montevideo, Uruguay
Duration: Mar 31 2014Apr 4 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8392 LNCS

Other

Other11th Latin American Theoretical Informatics Symposium, LATIN 2014
Country/TerritoryUruguay
CityMontevideo
Period3/31/144/4/14

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Budget feasible mechanisms for experimental design'. Together they form a unique fingerprint.

Cite this