Budget feasible mechanisms for experimental design

Thibaut Horel, Stratis Ioannidis, S. Muthukrishnan

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


    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
    Number of pages12
    ISBN (Print)9783642544224
    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
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Conference11th Latin American Theoretical Informatics Symposium, LATIN 2014

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


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

    Cite this