de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Forschungspapier

Near-optimal Asymmetric Binary Matrix Partitions

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons43960

Abed,  Fidaa
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

arXiv:1407.8170.pdf
(Preprint), 139KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0024-467B-5
Zusammenfassung
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.