Parameterized complexity of configuration integer programs

Abstrakt

Configuration integer programs (IP) have been key in the design of algorithms for NP-hard high-multiplicity problems. First, we develop fast exact (exponential-time) algorithms for Configuration IP and matching hardness results.

Second, we showcase the implications of these results to bin-packing and facility-location-like problems. (C) 2021 The Author(s). Published by Elsevier B.V.

Klíčová slova

• Parameterized algorithms
• Configuration IP
• Surfing