### Abstract

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 = {S_{1},...,S_{n}} consists of a partition S_{1} of [m] for each row i of the matrix. The partition S_{1} 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 language | English (US) |
---|---|

Title of host publication | Web and Internet Economics - 9th International Conference, WINE 2013, Proceedings |

Pages | 1-14 |

Number of pages | 14 |

DOIs | |

State | Published - Dec 1 2013 |

Externally published | Yes |

Event | 9th International Conference on Web and Internet Economics, WINE 2013 - Cambridge, MA, United States Duration: Dec 11 2013 → Dec 14 2013 |

### Publication series

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

Volume | 8289 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

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

Country | United States |

City | Cambridge, MA |

Period | 12/11/13 → 12/14/13 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

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

## Cite this

*Web and Internet Economics - 9th International Conference, WINE 2013, Proceedings*(pp. 1-14). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8289 LNCS). https://doi.org/10.1007/978-3-642-45046-4_1