Near-optimal asymmetric binary matrix partitions

DOI10.1007/S00453-016-0238-4MaRDI QIDQ1702119zbMATH OpenOpenAlexFDO

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

Publication date 28 February 2018

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL 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)

Recommendations

• Near-optimal asymmetric binary matrix partitions
• The asymmetric matrix partition problem
• Partitioning a matrix to minimize the maximum cost
• Approximations for the general block distribution of a matrix
• Approximation algorithms for \(k\)-partitioning problems with partition matroid constraint

Cites work

• scientific article; zbMATH DE number 3014822 (Why is no real title available?)
• 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
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Inapproximability results for combinatorial auctions with submodular utility functions
• Oblivious algorithms for the maximum directed cut problem
• Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
• 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
• Tight approximation bounds for combinatorial frugal coverage algorithms
• Wavelength management in WDM rings to maximize the number of connections

Cited in

(3)

• Near-optimal asymmetric binary matrix partitions
• The asymmetric matrix partition problem
• Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship

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 Q1702119)