Abed, Fidaa and Caragiannis, Ioannis and Voudouris, Alexandros A (2018) Near-Optimal Asymmetric Binary Matrix Partitions. Algorithmica, 80 (1). pp. 48-72. DOI https://doi.org/10.1007/s00453-016-0238-4
Abed, Fidaa and Caragiannis, Ioannis and Voudouris, Alexandros A (2018) Near-Optimal Asymmetric Binary Matrix Partitions. Algorithmica, 80 (1). pp. 48-72. DOI https://doi.org/10.1007/s00453-016-0238-4
Abed, Fidaa and Caragiannis, Ioannis and Voudouris, Alexandros A (2018) Near-Optimal Asymmetric Binary Matrix Partitions. Algorithmica, 80 (1). pp. 48-72. DOI https://doi.org/10.1007/s00453-016-0238-4
Abstract
We study the asymmetric binary matrix partition problem that was recently introduced by Alon et al. (Proceedings of the 9th Conference on Web and Internet Economics (WINE), pp 1–14, 2013). Instances of the problem consist of an n× m binary matrix A and a probability distribution over its columns. A partition schemeB= (B1, … , Bn) consists of a partition Bifor each row i of A. The partition Biacts as a smoothing operator on row i that distributes the expected value of each partition subset proportionally to all its entries. Given a scheme B that induces a smooth matrix AB, the partition value is the expected maximum column entry of AB. The objective is to find a partition scheme such that the resulting partition value is maximized. We present a 9/10-approximation algorithm for the case where the probability distribution is uniform and a (1 - 1 / e) -approximation algorithm for non-uniform distributions, significantly improving results of Alon et al. Although our first algorithm is combinatorial (and very simple), the analysis is based on linear programming and duality arguments. In our second result we exploit a nice relation of the problem to submodular welfare maximization.
Item Type: | Article |
---|---|
Additional Information: | 17 pages |
Uncontrolled Keywords: | cs.GT; cs.CC |
Divisions: | Faculty of Science and Health Faculty of Science and Health > Computer Science and Electronic Engineering, School of |
SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
Depositing User: | Unnamed user with email elements@essex.ac.uk |
Date Deposited: | 20 May 2020 11:58 |
Last Modified: | 30 Oct 2024 16:17 |
URI: | http://repository.essex.ac.uk/id/eprint/27261 |
Available files
Filename: abmp.algo.2018.pdf