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

DOI10.1016/J.TCS.2011.09.018MaRDI QIDQ655417zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Approximation and Online Algorithms
• Approximation algorithms for covering/packing integer programs
• Approximating covering integer programs with multiplicity constraints
• On approximating (sparse) covering integer programs
• Approximation schemes for packing splittable items with cardinality constraints

Cites work

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

Cited in

(1)

• Approximation and Online Algorithms

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q655417)