Home

Shaddin Dughmi

  1. Combinatorial Auctions with Restricted Complements.

    Mon, 05/21/2012 - 15:01 — SomNambul
    Authors: Moshe Babaioff, Tim Roughgarden, Shaddin Dughmi, Ittai Abraham
    Subjects: Computer Science and Game Theory
    Abstract

    Complements between goods - where one good takes on added value in the
    presence of another - have been a thorn in the side of algorithmic mechanism
    designers. On the one hand, complements are common in the standard motivating
    applications for combinatorial auctions, like spectrum license auctions. On the
    other, welfare maximization in the presence of complements is notoriously
    difficult, and this intractability has stymied theoretical progress in the
    area.

  2. Truthful Assignment without Money.

    Tue, 01/05/2010 - 16:02 — SomNambul
    Authors: Arpita Ghosh, Shaddin Dughmi
    Subjects: Computer Science and Game Theory
    Abstract

    We study the design of truthful mechanisms that do not use payments for the
    generalized assignment problem (GAP) and its variants. An instance of the GAP
    consists of a bipartite graph with jobs on one side and machines on the other.
    Machines have capacities and edges have values and sizes; the goal is to
    construct a welfare maximizing feasible assignment. In our model of private
    valuations, motivated by impossibility results, the value and sizes on all
    job-machine pairs are public information; however, whether an edge exists or
    not in the bipartite graph is a job's private information.

  3. Amplified Hardness of Approximation for VCG-Based Mechanisms.

    Mon, 12/21/2009 - 16:01 — SomNambul
    Authors: Robert Kleinberg, Shaddin Dughmi, Hu Fu
    Subjects: Computer Science and Game Theory
    Abstract

    If a two-player social welfare maximization problem does not admit a PTAS, we
    prove that any maximal-in-range truthful mechanism that runs in polynomial time
    cannot achieve an approximation factor better than 1/2. Moreover, for the
    k-player version of the same problem, the hardness of approximation improves to
    1/k under the same two-player hardness assumption.

  4. Space Constrained Dynamic Covering.

    Tue, 12/15/2009 - 16:01 — SomNambul
    Authors: Anish Das Sarma, Shaddin Dughmi, Ioannis Antonellis
    Subjects: Data Structures and Algorithms
    Abstract

    In this paper, we identify a fundamental algorithmic problem that we term
    space-constrained dynamic covering (SCDC), arising in many modern-day web
    applications, including ad-serving and online recommendation systems in eBay
    and Netflix. Roughly speaking, SCDC applies two restrictions to the
    well-studied Max-Coverage problem: Given an integer k, X={1,2,...,n} and
    I={S_1, ..., S_m}, S_i a subset of X, find a subset J of I, such that |J| <= k
    and the union of S in J is as large as possible.

  5. Submodular Functions: Extensions, Distributions, and Algorithms. A Survey.

    Thu, 12/03/2009 - 16:01 — SomNambul
    Authors: Shaddin Dughmi
    Subjects: Data Structures and Algorithms
    Abstract

    Submodularity is a fundamental phenomenon in combinatorial optimization.
    Submodular functions occur in a variety of combinatorial settings such as
    coverage problems, cut problems, welfare maximization, and many more.
    Therefore, a lot of work has been concerned with maximizing or minimizing a
    submodular function, often subject to combinatorial constraints. Many of these
    algorithmic results exhibit a common structure.

Math-arch

Syndicate content