Home

Allan Borodin

  1. Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates.

    Fri, 03/30/2012 - 15:01 — SomNambul
    Authors: Allan Borodin, Yuli Ye, Hyun Chul Lee
    Subjects: Data Structures and Algorithms
    Abstract

    Result diversification has many important applications in databases,
    operations research, information retrieval, and finance. In this paper, we
    study and extend a particular version of result diversification, known as
    max-sum diversification. More specifically, we consider the setting where we
    are given a set of elements in a metric space and a set valuation function $f$
    defined on every subset. For any given subset $S$, the overall objective is a
    linear combination of $f(S)$ and the sum of the distances induced by $S$.

  2. Price of Anarchy for Greedy Auctions.

    Mon, 09/07/2009 - 22:13 — SomNambul
    Authors: Brendan Lucier, Allan Borodin
    Subjects: Computer Science and Game Theory
    Abstract

    We consider mechanisms for utilitarian combinatorial allocation problems,
    where agents are not assumed to be single-minded. This class of problems
    includes combinatorial auctions, multi-unit auctions, unsplittable flow
    problems, profit-maximizing scheduling, and others. We study the price of
    anarchy for such mechanisms, which is a bound on the approximation ratio
    obtained at any mixed Nash equilibrium. We demonstrate that a broad class of
    greedy approximation algorithms can be implemented as mechanisms for which the
    price of anarchy nearly matches the performance of the original algorithm.

Math-arch

Syndicate content