Approximation algorithms for a class of resource constrained network optimization problems.

摘要

Resource-constrained network optimization problems arise in all areas of business and technology. In particular, network optimization problems find numerous applications in communication network design, production and inventory planning, transportation, facilities location and allocation, airline scheduling and satellite communication, robotics and many other areas. Network problems like resource-constrained path and resource-constrained spanning tree are widely studied, while other problems like resource-constrained perfect matching and resource-constrained Chinese postman have not so far received sufficient treatment. Unfortunately, these problems belong to the class of computationally hard (NP-hard) problems for which no polynomial time algorithm is known. Therefore, the design of approximation algorithms that trade preciseness for efficiency has immense applied importance.; This dissertation deals with the design of an abstract model that addresses the class of weakly NP-hard resource-constrained network optimization problems, including but not limited to the resource-constrained path problem, resource-constrained spanning tree problem, resource-constrained cut problem, and resource-constrained perfect matching problem. The model unites scattered results into a single unified theory and provides efficient approximation algorithms with their performance guarantee for every particular problem of a wide class. The study provides a tool enabling the consideration of new problems as particular cases of the unified model. In addition, we introduce a conceptual multiset problem and investigate two instances of this problem, namely, the directed and undirected resource-constrained Chinese postman problems. The study shows that the model can be fully extended to the problems involving multisubsets of graph edges (at least to the directed version of the resource-constrained Chinese postman problem).