Near-optimal asymmetric binary matrix partitions

DOI10.1007/s00453-016-0238-4zbMath1387.68295OpenAlexW3021212255MaRDI QIDQ1702119

Fidaa Abed, Alexandros A. Voudouris, Ioannis Caragiannis

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

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

Related Items (1)

Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs
• Inapproximability results for combinatorial auctions with submodular utility functions
• Simplified mechanisms with an application to sponsored-search auctions
• Oblivious algorithms for the maximum directed cut problem
• Tight approximation bounds for combinatorial frugal coverage algorithms
• Combinatorial auctions with decreasing marginal utilities
• The Asymmetric Matrix Partition Problem
• An Improved Approximation Bound for Spanning Star Forest and Color Saving
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• A Theory of Auctions and Competitive Bidding
• Strategic Information Transmission
• Online bipartite matching with random arrivals
• Wavelength Management in WDM Rings to Maximize the Number of Connections

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