Parameterized complexity of configuration integer programs |
| |
| Affiliation: | 1. Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Prague, Czech Republic;2. Charles University, Prague, Czech Republic;3. Technion – Israel Institute of Technology, Haifa, Israel;4. Hamburg University of Technology, Institute for Algorithms and Complexity, Hamburg, Germany |
| |
| Abstract: | 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. |
| |
| Keywords: | Parameterized algorithms Configuration IP Surfing |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
