Matching Problem Under Linear Constraint

The matching problem is a classic combination optimization problem with a long history.In past studies,lots of efficient algorithms for matching problems and their derivatives have been given.These results have been widely used in various scenes of production and life.Linear programming is an optimization problem in which both constraints and targets are linear functions.It is an important research area for optimization problems.Many scholars have also proposed and improved various algorithms to efficiently solve linear programming.In traditional research,the parameters of the matching problem are generally used as inputs and do not participate in the process of optimizing.However,in practical ap-plications,such parameters are often solutions to some optimization problems.Matching problems are no exception.For these parameters,we try to use linear constraints to char-acterize the various constraints in the application scenario,so that the matching problem under linear constraints can be obtained.By studying the matching problem under linear constraints,the loss of information in the parameter selection process can be avoided.This paper discusses the complexity of the maximum weight matching problem under linear constraints in general conditions in the first part.Then we give some generalization of the results.For some specific cases,we give exact or approximate algorithms through some techniques of linear programming.This paper focuses on the combination of parameter selection in linear programming and matching problems,and has done some research on some specific situations.The main innovations of this paper are:·We propose the matching problem under linear constraints,and proved that the maximum weight matching problem under linear constraints is NP-hard,although the maximum weight matching problem has a strong polynomial algorithm.For the minimize weight perfect match under linear constraints,the result of no arbitrary constant approximation is obtained.·The PTAS algorithm under the constant class edge weight is given.The PTAS algorithm is given for the case where the edge weight satisfies the specific condition,and the optimal solution with additional unique constraints is given.For the case of constant constraints,the most can be obtained.The polynomial algorithm of the solution is given,and the general algorithm of 1/k-approximation is given.