Near-optimal asymmetric binary matrix partitions

DOI10.1007/978-3-662-48054-0_1MaRDI QIDQ2946372zbMATH OpenOpenAlexFDO

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)

Full work available at URL https://arxiv.org/abs/1407.8170, http://repository.essex.ac.uk/27261/1/abmp.algo.2018.pdf

Mathematics Subject Classification ID

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

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.

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

Cites work

• A Theory of Auctions and Competitive Bidding
• An Improved Approximation Bound for Spanning Star Forest and Color Saving
• Analysis of approximation algorithms for k-set cover using factor-revealing linear programs
• Combinatorial auctions with decreasing marginal utilities
• Full Extraction of the Surplus in Bayesian and Dominant Strategy Auctions
• Inapproximability results for combinatorial auctions with submodular utility functions
• 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
• Strategic Information Transmission
• The asymmetric matrix partition problem
• The submodular welfare problem with demand queries
• The value of information in a sealed-bid auction
• Tight approximation bounds for combinatorial frugal coverage algorithms
• Wavelength management in WDM rings to maximize the number of connections

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)