Skip to main content

and
  1. No Access

    Chapter and Conference Paper

    Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack

    In this paper, we study the integrality gap of the Knapsack linear program in the Sherali-Adams and Lasserre hierarchies. First, we show that an integrality gap of 2 – ε persists up to a linear number of rounds o...

    Anna R. Karlin, Claire Mathieu in Integer Programming and Combinatoral Optim… (2011)

  2. Chapter and Conference Paper

    Ad Auctions – Current and Future Research

    An exploding market has emerged during the last few years on the internet, the market of sponsored search slots. Advertisers are able to buy space on the webpages produced by popular search engines and place a...

    Anna R. Karlin in Algorithmic Aspects in Information and Management (2007)

  3. No Access

    Chapter and Conference Paper

    Mechanism Design for Fun and Profit

    The emergence of the Internet as one of the most important arenas for resource sharing between parties with diverse and selfish interests has led to a number of fascinating and new algorithmic problems. In the...

    Anna R. Karlin in Algorithms — ESA 2002 (2002)

  4. No Access

    Chapter and Conference Paper

    Truthful and Competitive Double Auctions

    In this paper we consider the problem of designing a mechanism for double auctions where bidders each bid to buy or sell one unit of a single commodity. We assume that each bidder’s utility value for the item ...

    Kaustubh Deshmukh, Andrew V. Goldberg, Jason D. Hartline in Algorithms — ESA 2002 (2002)