TY - GEN

T1 - The asymmetric matrix partition problem

AU - Alon, Noga

AU - Feldman, Michal

AU - Gamzu, Iftah

AU - Tennenholtz, Moshe

PY - 2013/12/1

Y1 - 2013/12/1

N2 - An instance of the asymmetric matrix partition problem consists of a matrix A ∈ R+nxm 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 S = {S1,...,Sn} consists of a partition S1 of [m] for each row i of the matrix. The partition S1 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 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.

AB - An instance of the asymmetric matrix partition problem consists of a matrix A ∈ R+nxm 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 S = {S1,...,Sn} consists of a partition S1 of [m] for each row i of the matrix. The partition S1 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 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.

UR - http://www.scopus.com/inward/record.url?scp=84893058817&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84893058817&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-45046-4_1

DO - 10.1007/978-3-642-45046-4_1

M3 - Conference contribution

AN - SCOPUS:84893058817

SN - 9783642450457

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1

EP - 14

BT - Web and Internet Economics - 9th International Conference, WINE 2013, Proceedings

T2 - 9th International Conference on Web and Internet Economics, WINE 2013

Y2 - 11 December 2013 through 14 December 2013

ER -