skip to main content
10.5555/1109557.1109624acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
Article

Tight approximation algorithms for maximum general assignment problems

Published: 22 January 2006 Publication History

Abstract

A separable assignment problem (SAP) is defined by a set of bins and a set of items to pack in each bin; a value, fij, for assigning item j to bin i; and a separate packing constraint for each bin - i.e. for bin i, a family Li of subsets of items that fit in bin i. The goal is to pack items into bins to maximize the aggregate value. This class of problems includes the maximum generalized assignment problem (GAP)1) and a distributed caching problem (DCP) described in this paper.Given a β-approximation algorithm for finding the highest value packing of a single bin, we give1. A polynomial-time LP-rounding based ((1 − 1/e)β)-approximation algorithm.2. A simple polynomial-time local search (β/β+1 - ε) - approximation algorithm, for any ε > 0.Therefore, for all examples of SAP that admit an approximation scheme for the single-bin problem, we obtain an LP-based algorithm with (1 - 1/e - ε)-approximation and a local search algorithm with (1/2-ε)-approximation guarantee. Furthermore, for cases in which the subproblem admits a fully polynomial approximation scheme (such as for GAP), the LP-based algorithm analysis can be strengthened to give a guarantee of 1 - 1/e. The best previously known approximation algorithm for GAP is a 1/2-approximation by Shmoys and Tardos; and Chekuri and Khanna. Our LP algorithm is based on rounding a new linear programming relaxation, with a provably better integrality gap.To complement these results, we show that SAP and DCP cannot be approximated within a factor better than 1 -1/e unless NP⊆ DTIME(nO(log log n)), even if there exists a polynomial-time exact algorithm for the single-bin problem.We extend the (1 - 1/e)-approximation algorithm to a nonseparable assignment problem with applications in maximizing revenue for budget-constrained combinatorial auctions and the AdWords assignment problem. We generalize the local search algorithm to yield a 1/2-ε approximation algorithm for the k-median problem with hard capacities. Finally, we study naturally defined game-theoretic versions of these problems, and show that they have price of anarchy of 2. We also prove the existence of cycles of best response moves, and exponentially long best-response paths to (pure or sink) equilibria.

References

[1]
A. A. Ageev and M. I. Sviridenko. Pipage rounding: A new method of constructing algorithms with proven performance guarantee. J. of Combinatorial Optimization, 8:307--328, 2004.]]
[2]
N. Andelman and Y. Mansour. Auctions with budget constraints. In SWAT, 2004.]]
[3]
I. D. Baev and R. Rajaraman. Approximation algorithms for data placement in arbitrary networks. In 12th ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 661--670, 2001.]]
[4]
B. Carr and S. Vempala. Randomized meta-rounding. Random Structure and Algorithms, 20(3):343--352, 2002.]]
[5]
C. Chekuri. Personal communication. 2005.]]
[6]
C. Chekuri and S. Khanna. A PTAS for the multiple knapsack problem. In 11th ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 213--222, 2000.]]
[7]
U. Feige. A threshold of In n for approximating set cover. Journal of the ACM, 45(4):634--652, 1998.]]
[8]
U. Feige, M. M. Halldorsson, G. Kortsarz, and A. Srinivasan. Approximating the domatic number. SIAM Journal of Computing, 32(1):172--195, 2002.]]
[9]
U. Feige and G. Kortsarz. Personal communication. 2005.]]
[10]
M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey. An analysis of the approximations for maximizing submodular set functions II. Mathematical Programming Study, 8:73--87, 1978.]]
[11]
N. Garg and J. Könemann. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. In 39th Annual IEEE Symposium on Foundations of Computer Science, pages 300--309, 1998.]]
[12]
R. Garg, V. Kumar, and V. Pandit. Approximation algorithms for budget-constrained auctions. In 4th International Work-shop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2001.]]
[13]
M. Goemans, L. Li, V. S. Mirrokni, and M. Thottan. Market sharing games applied to content distribution in ad-hoc networks. In 5th ACM International Symp. on Mobile Ad Hoc Networking and Computing (MobiHoc), 2004.]]
[14]
M. Goemans, V. S. Mirrokni, and A. Vetta. Sink equilibria and convergence. In FOCS, 2005.]]
[15]
M. X. Goemans and D. P. Williamson. New 3/4-approximation algorithms for the maximum satisfiability problem. SIAM Journal of Discrete Mathematics, 7:656--666, 1994.]]
[16]
C. Gomes, R. Regis, and D. Shmoys. An improved approximation algorithm for the partial Latin square extension problem. In 14th ACM-SIAM Symp. on Discrete Algorithms (SODA), 2003.]]
[17]
K. Jain, M. Mahdian, and M. Salavatipour. Packing stiner trees. In 14th ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 266--274, 2003.]]
[18]
K. Jansen and G. Zhang. On rectangle packing: maximizing benefits. In 15th ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 204--213, 2004.]]
[19]
D. Johnson, C. H. Papadimitriou, and M. Yannakakis. How easy is local search? Journal of Computer and System Sciences, 37:79--100, 1988.]]
[20]
V. S. Mirrokni. Approximation Algorithms for Distributed and Selfish Agents. MIT Thesis, 2005.]]
[21]
J. F. Nash. Equilibrium points in N-person games. In Proceedings of NAS, 1950.]]
[22]
Z. Nutov, I. Beniaminy, and R. Yuster. A (1-1/e)-approximation algorithm for the maximum profit generalized assignment problem with fixed profits. Operations Research Letters. To appear.]]
[23]
C.H. Papadimitriou, A. Schaffer, and M. Yannakakis. On the complexity of local search. In 22nd Symp. on Theory of Computing (STOC), pages 438--445, 1990.]]
[24]
E. Petrank. The hardness of approximation: Gap location. In Computational Complexity, pages 133--137, 1994.]]
[25]
S. A. Plotkin, D. Shmoys, and É. Tardos. Fast approximation algorithms for fractional packing and covering problems. Mathematics of Operations Research, 20:257--301, 1995.]]
[26]
A. Schaffer and M. Yannakakis. Simple local search problems that are hard to solve. SIAM journal on Computing, 20(1):56--87, 1991.]]
[27]
H. Shachnai and T. Tamir. Approximation schemes for generalized 2-dimensional vector packing with application to data placement. In 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 167--177, 2003.]]
[28]
D. Shmoys and E. Tardos. An approximation algorithm for the generalized assignment problem. Mathematical Programming, 62(3):461--474, 1993.]]
[29]
A. Srinivasan. Distributions on level-sets with applications to approximation algorithms. In 44th Symp. on Foundations of Computer Science (FOCS), pages 588--597, 2001.]]
[30]
M. Sviridenko. A note on maximizing a submodular set function subject to knapsack constraint. Operations Research Letters, 32:41--43, 2004.]]
[31]
C. Swamy. Algorithms for the data placement problem. Unpublished, 2004.]]
[32]
A. Vetta. Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions. In 43rd Symp. on Foundations of Computer Science (FOCS), pages 416--425, 2002.]]
[33]
N. Young. Randomized rounding without solving the linear program. In 7th ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 170--178, 1996.]]
[34]
N. Young. Sequential and parallel algorithms for mixed packing and covering. In 42nd Annual IEEE Symposium on Foundations of Computer Science, pages 538--546, 2001.]]

Cited By

View all
  • (2023)Diverse approximations for monotone submodular maximization problems with a matroid constraintProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/617(5558-5566)Online publication date: 19-Aug-2023
  • (2021)Efficient Schedule of Energy-Constrained UAV Using Crowdsourced Buses in Last-Mile Parcel DeliveryProceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies10.1145/34480795:1(1-23)Online publication date: 30-Mar-2021
  • (2019)Online Submodular Maximization with PreemptionACM Transactions on Algorithms10.1145/330976415:3(1-31)Online publication date: 7-Jun-2019
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm
January 2006
1261 pages
ISBN:0898716055

Sponsors

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 22 January 2006

Check for updates

Qualifiers

  • Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)20
  • Downloads (Last 6 weeks)1
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Diverse approximations for monotone submodular maximization problems with a matroid constraintProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/617(5558-5566)Online publication date: 19-Aug-2023
  • (2021)Efficient Schedule of Energy-Constrained UAV Using Crowdsourced Buses in Last-Mile Parcel DeliveryProceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies10.1145/34480795:1(1-23)Online publication date: 30-Mar-2021
  • (2019)Online Submodular Maximization with PreemptionACM Transactions on Algorithms10.1145/330976415:3(1-31)Online publication date: 7-Jun-2019
  • (2019)Distributed approximation of k-service assignmentDistributed Computing10.1007/s00446-017-0321-332:1(27-40)Online publication date: 1-Feb-2019
  • (2018)Online Submodular Maximization with Free DisposalACM Transactions on Algorithms10.1145/324277014:4(1-29)Online publication date: 17-Sep-2018
  • (2018)Charging Task Scheduling for Directional Wireless Charger NetworksProceedings of the 47th International Conference on Parallel Processing10.1145/3225058.3225080(1-10)Online publication date: 13-Aug-2018
  • (2018)Congestion Avoidance and Load Balancing in Content Placement and Request Redirection for Mobile CDNIEEE/ACM Transactions on Networking10.1109/TNET.2018.280497926:2(851-863)Online publication date: 1-Apr-2018
  • (2018)Adaptive Caching Networks With Optimality GuaranteesIEEE/ACM Transactions on Networking10.1109/TNET.2018.279358126:2(737-750)Online publication date: 1-Apr-2018
  • (2018)Performance Bounds with Curvature for Batched Greedy OptimizationJournal of Optimization Theory and Applications10.1007/s10957-017-1177-1177:2(535-562)Online publication date: 1-May-2018
  • (2017)Online submodular maximization with free disposalProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039764(1204-1223)Online publication date: 16-Jan-2017
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media