Near-optimal asymmetric binary matrix partitions

DOI10.1007/978-3-662-48054-0_1zbMATH Open1387.68294arXiv1407.8170OpenAlexW1558735371MaRDI QIDQ2946372FDOQ2946372

Authors: Fidaa Abed, I. Caragiannis, Alexandros A. Voudouris 

Publication date: 16 September 2015

Published in: Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

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 $nimesm$ binary matrix $A$ and a probability distribution over its columns. A partition scheme $B=(B_1,\mathrm{...},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.

Full work available at URL: https://arxiv.org/abs/1407.8170

Recommendations

• Near-optimal asymmetric binary matrix partitions
• The asymmetric matrix partition problem
• On the computational complexity of optimal simple mechanisms
• Approximate revenue maximization with multiple items
• On revenue maximization for selling multiple independently distributed items

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorics in computer science (68R05) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites Work

• Full Extraction of the Surplus in Bayesian and Dominant Strategy Auctions
• A Theory of Auctions and Competitive Bidding
• Strategic Information Transmission
• Combinatorial auctions with decreasing marginal utilities
• The value of information in a sealed-bid auction
• Optimal Selling Strategies under Uncertainty for a Discriminating Monopolist when Demands are Interdependent
• Optimal approximation for the submodular welfare problem in the value oracle model
• Simplified mechanisms with an application to sponsored-search auctions
• An Improved Approximation Bound for Spanning Star Forest and Color Saving
• Inapproximability results for combinatorial auctions with submodular utility functions
• Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs
• Wavelength management in WDM rings to maximize the number of connections
• Tight approximation bounds for combinatorial frugal coverage algorithms
• The submodular welfare problem with demand queries
• The asymmetric matrix partition problem

Cited In (2)

• Near-optimal asymmetric binary matrix partitions
• The asymmetric matrix partition problem

This page was built for publication: Near-optimal asymmetric binary matrix partitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946372)