The asymmetric matrix partition problem

Noga Alon, Michal Feldman, Iftah Gamzu, Moshe Tennenholtz

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationWeb and Internet Economics - 9th International Conference, WINE 2013, Proceedings
Number of pages14
StatePublished - 2013
Externally publishedYes
Event9th International Conference on Web and Internet Economics, WINE 2013 - Cambridge, MA, United States
Duration: Dec 11 2013Dec 14 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8289 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other9th International Conference on Web and Internet Economics, WINE 2013
Country/TerritoryUnited States
CityCambridge, MA

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'The asymmetric matrix partition problem'. Together they form a unique fingerprint.

Cite this