A fast approximation algorithm for solving the complete set packing problem

DOI10.1016/J.EJOR.2014.01.024MaRDI QIDQ2514810zbMATH OpenOpenAlexFDO

Authors Tri-Dung Nguyen

Publication date 4 February 2015

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://eprints.soton.ac.uk/361100/1/Complete_Set_Packing_Problem2.pdf

zbMATH Keywords

set packing problemwinner determination problemcombinatorial auctionscoalition structure generationlarge-scale MILP

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Cooperative games (91A12) Auctions, bargaining, bidding and selling, and other market models (91B26) Approximation algorithms (68W25) Mixed integer programming (90C11)

Recommendations

• A hybrid exact algorithm for complete set partitioning
• Solving the set packing problem via a maximum weighted independent set heuristic
• Alternative formulations for the set packing problem and their application to the winner determination problem
• Large neighborhood local search for the maximum set packing problem
• A branch-and-price algorithm and new test problems for spectrum auctions

Cites work

• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 1323118 (Why is no real title available?)
• A genetic algorithm for the set covering problem
• A new approach for modeling and solving set packing problems
• A new modeling and solution approach for the set-partitioning problem
• A polynomial case of unconstrained zero-one quadratic optimization
• A set packing approach for scheduling elective surgical procedures
• A unified modeling and solution framework for combinatorial optimization problems
• Algorithm for optimal winner determination in combinatorial auctions
• Algorithmic Aspects of the Core of Combinatorial Optimization Games
• Algorithms for the set covering problem
• An algorithm for set covering problem
• Anytime coalition structure generation in multi-agent systems with positive or negative externalities
• Coalition structure generation with worst case guarantees
• Combinatorial auctions: a survey
• Computationally manageable combinational auctions
• Computing power indices for large voting games
• Enhancing an algorithm for set covering problems
• GRASP for set packing problems.
• Geometric algorithms and combinatorial optimization.
• New facets for the set packing polytope
• On the facial structure of set packing polyhedra
• Online set packing
• Routing trains through a railway station based on a node packing model

Cited in

(5)

• Upper bounds on the average number of iterations for some algorithms of solving the set packing problem
• Fast First-Order Algorithms for Packing–Covering Semidefinite Programs
• A faster parameterized algorithm for set packing
• An evolutionary algorithm based hyper-heuristic framework for the set packing problem
• Alternative formulations for the set packing problem and their application to the winner determination problem

Describes a project that uses

Uses Software

• CPLEX

This page was built for publication: A fast approximation algorithm for solving the complete set packing problem

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