2013 | OriginalPaper | Buchkapitel
The Asymmetric Matrix Partition Problem
verfasst von : Noga Alon, Michal Feldman, Iftah Gamzu, Moshe Tennenholtz
Erschienen in: Web and Internet Economics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
An instance of the asymmetric matrix partition problem consists of a matrix
$A \in \mathbb{R}_+^{n \times m}$
and a probability distribution
p
over its columns. The goal is to find a partition scheme that maximizes the resulting partition value. A partition scheme
$\mathcal{S} = \{ \mathcal{S}_1, \ldots, \mathcal{S}_{n}\}$
consists of a partition
$\mathcal{S}_i$
of [
m
] for each row
i
of the matrix. The partition
$\mathcal{S}_i$
can be interpreted as a smoothing operator on row
i
, which replaces the value of each entry in that row with the expected value in the partition subset that contains it. Given a scheme
$\mathcal{S}$
that induces a smoothed matrix
A
′, the partition value is the expected maximum column entry of
A
′.
We establish that this problem is already APX-hard for the seemingly simple setting in which
A
is binary and
p
is uniform. We then demonstrate that a constant factor approximation can be achieved in most cases of interest. Later on, we discuss the symmetric version of the problem, in which one must employ an identical partition for all rows, and prove that it is essentially trivial. Our matrix partition problem draws its interest from several applications like broad matching in sponsored search advertising and information revelation in market settings. We conclude by discussing the latter application in depth.