Approximation schemes for deal splitting and covering integer programs with multiplicity constraints

DOI10.1016/j.tcs.2011.09.018zbMath1229.90165OpenAlexW2134024389MaRDI QIDQ655417

Ariel Kulik, Hadas Shachnai, Oded Shmueli, Robert Sayegh

Publication date: 4 January 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.09.018

zbMATH Keywords

approximation algorithmsreverse auctionscovering integer programsdeal splittingmulti-dimensional knapsack

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27) Auctions, bargaining, bidding and selling, and other market models (91B26) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Hard multidimensional multiple choice knapsack problems, an empirical study
• There is no EPTAS for two-dimensional knapsack
• Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
• Scatter search algorithm for supplier selection and order lot sizing under multiple price discount environment
• Exact algorithms for procurement problems under a total quantity discount structure
• Approximate algorithms for some generalized knapsack problems
• Approximating covering integer programs with multiplicity constraints
• Heuristics for sourcing from multiple suppliers with alternative quantity discounts
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximability of Sparse Integer Programs
• APPROXIMATE ALGORITHMS FOR THE MULTIPLE-CHOICE CONTINUOUS KNAPSACK PROBLEMS
• A Greedy Heuristic for the Set-Covering Problem
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
• THE MULTIPLE-CHOICE KNAPSACK PROBLEM
• Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
• Improved Approximation Guarantees for Packing and Covering Integer Programs
• Improved Multi-unit Auction Clearing Algorithms with Interval (Multiple-Choice) Knapsack Problems
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques

This page was built for publication: Approximation schemes for deal splitting and covering integer programs with multiplicity constraints