English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Near-optimal Asymmetric Binary Matrix Partitions

Abed, F., Caragiannis, I., & Voudouris, A. A. (2014). Near-optimal Asymmetric Binary Matrix Partitions. Retrieved from http://arxiv.org/abs/1407.8170.

Item is

Files

show Files
hide Files
:
arXiv:1407.8170.pdf (Preprint), 139KB
Name:
arXiv:1407.8170.pdf
Description:
File downloaded from arXiv at 2014-12-02 12:57
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-

Locators

show

Creators

show
hide
 Creators:
Abed, Fidaa1, Author           
Caragiannis, Ioannis2, Author
Voudouris, Alexandros A.2, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Content

show
hide
Free keywords: Computer Science, Computer Science and Game Theory, cs.GT,Computer Science, Computational Complexity, cs.CC
 Abstract: We study the asymmetric binary matrix partition problem that was recently introduced by Alon et al. (WINE 2013) to model the impact of asymmetric information on the revenue of the seller in take-it-or-leave-it sales. Instances of the problem consist of an $n \times m$ binary matrix $A$ and a probability distribution over its columns. A partition scheme $B=(B_1,...,B_n)$ consists of a partition $B_i$ for each row $i$ of $A$. The partition $B_i$ acts 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 $A^B$, the partition value is the expected maximum column entry of $A^B$. 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.

Details

show
hide
Language(s): eng - English
 Dates: 2014-07-302014-07-30
 Publication Status: Published online
 Pages: 15 pages
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: arXiv: 1407.8170
URI: http://arxiv.org/abs/1407.8170
BibTex Citekey: DBLP:journals/corr/AbedCV14
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show