A linear programming based approach to the Steiner tree problem with a fixed number of terminals

Autor: Matías Siebert, Shabbir Ahmed, George L. Nemhauser
Rok vydání: 2019
Předmět:
FOS: Computer and information sciences
Convex hull
Polynomial
Discrete Mathematics (cs.DM)
Linear programming
Computer Networks and Communications
0211 other engineering and technologies
02 engineering and technology
Steiner tree problem
symbols.namesake
Integer
Computer Science - Data Structures and Algorithms
0502 economics and business
FOS: Mathematics
Hardware_INTEGRATEDCIRCUITS
Mathematics - Combinatorics
Data Structures and Algorithms (cs.DS)
Computer Science::Data Structures and Algorithms
Integer programming
Mathematics
Discrete mathematics
050210 logistics & transportation
021103 operations research
05 social sciences
Hardware and Architecture
symbols
Graph (abstract data type)
Combinatorics (math.CO)
Relaxation (approximation)
Software
Computer Science - Discrete Mathematics
Information Systems
Zdroj: Networks. 75:124-136
ISSN: 1097-0037
0028-3045
DOI: 10.1002/net.21913
Popis: We present a set of integer programs (IPs) for the Steiner tree problem with the property that the best solution obtained by solving all, provides an optimal Steiner tree. Each IP is polynomial in the size of the underlying graph and our main result is that the linear programming (LP) relaxation of each IP is integral so that it can be solved as a linear program. However, the number of IPs grows exponentially with the number of terminals in the Steiner tree. As a consequence, we are able to solve the Steiner tree problem by solving a polynomial number of LPs, when the number of terminals is fixed.
Databáze: OpenAIRE
Externí odkaz: