Abstract
In this paper, we study several graph optimization problems in which the weights of vertices or edges are variables determined by several linear constraints, including the maximum matching problem under linear constraints (max-MLC), the minimum perfect matching problem under linear constraints (min-PMLC), the shortest path problem under linear constraints (SPLC) and the vertex cover problem under linear constraints (VCLC). The objective of these problems is to decide the weights that are feasible to the linear constraints, and to find the optimal solution of the graph optimization problems among all the feasible choices of weights. Even though all the original graph optimization problems can be solved in polynomial time or be approximated within a fixed constant factor, we find that these problems under linear constraints are intractable in general. In particular, we show that the max-MLC problem is NP-hard, while the min-PMLC, SPLC, VCLC problems are all NP-hard and do not even have any polynomial-time algorithms unless \(P = NP\). These findings suggest us to explore the special cases of these problems which are tractable. Particularly, we show that when the number of constraints is a fixed constant, all these problems under linear constraints are polynomially solvable. Moreover, if there are fixed number of distinct weights, then the max-MLC, min-PMLC and SPLC are polynomially solvable, and the VCLC has 2-approximation algorithm. In addition, we propose several approximation algorithms for max-MLC.
This work has been supported by NSFC No. 11801589, No. 11771245 and No. 11371216.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
All the results on this paper holds for G is a directed graph.
References
Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85–103 (1972)
Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Courier Dover Publications, New York (1998)
Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms, 4th edn. Springer, Heidelberg (2012)
Nip, K., Wang, Z., Wang, Z.: Scheduling under linear constraints. Eur. J. Oper. Res. 253(2), 290–297 (2016)
Nip, K., Wang, Z., Wang, Z.: Knapsack with variable weights satisfying linear constraints. J. Global Optim. 69(3), 713–725 (2017)
Wang, Z., Nip, K.: Bin packing under linear constraints. J. Comb. Optim. 34(5), 1198–1209 (2017)
Zhang, S., Nip, K., Wang, Z.: Related machine scheduling with machine speeds satisfying linear constraints. In: Kim, D., Uma, R.N., Zelikovsky, A. (eds.) COCOA 2018. LNCS, vol. 11346, pp. 314–328. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-04651-4_21
Burer, S., Letchford, A.N.: Non-convex mixed-integer nonlinear programming: a survey. Surv. Oper. Res. Manag. Sci. 17(2), 97–106 (2012)
Köppe, M.: On the complexity of nonlinear mixed-integer optimization. In: Lee, J., Leyffer, S. (eds.) Mixed-Integer Nonlinear Programming. IMA, vol. 154, pp. 533–558. Springer, Berlin (2011). https://doi.org/10.1007/978-1-4614-1927-3_19
Fagoyinbo, I., Ajibode, I.: Application of linear programming techniques in the effective use of resources for staff training. J. Emerg. Trends Eng. Appl. Sci. 1(2), 127–132 (2010)
Gupta, K.M.: Application of linear programming techniques for staff training. Int. J. Eng. Innov. Technol. 3(12), 132–135 (2014)
Uko, L.U., Lutz, R.J., Weisel, J.A.: An application of linear programming in performance evaluation. Acad. Educ. Lead. J. 21, 1–7 (2017)
Kleinberg, J., Tardos, É.: Algorithm Design. Pearson Education, Incorporated, New York (2006)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)
Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall, New Jersey (1993)
Kuhn, H.W.: The hungarian method for the assignment problem. Nav. Res. Logist. Q. 2(1 & 2), 83–97 (1955)
Burkard, R., Dell’Amico, M., Martello, S.: Assignment Problems. Society for Industrial and Applied Mathematics, Philadelphia (2009)
Edmonds, J.: A glimpse of heaven. In: Lenstra, J., Kan, A.R., Schrijver, A. (eds.) History of Mathematical Programming - A Collection of Personal Reminiscences, pp. 32–54. Centrum Wiskunde & Informatica, Amsterdam (1961)
Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17, 449–467 (1965)
Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1, 269–271 (1959)
Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 596–615 (1987)
Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, New York (2011)
Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. Math. 162(1), 439–485 (2005)
Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2-\(\epsilon \). J. Comput. Syst. Sci. 74(3), 335–349 (2008)
Luenberger, D.G., Ye, Y.: Linear and Nonlinear Programming. Springer, New York (2015)
Schrijver, A.: Theory of Linear and Integer Programming. Wiley, Incorporated, New York (1986)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Nip, K., Wang, Z., Shi, T. (2019). Some Graph Optimization Problems with Weights Satisfying Linear Constraints. In: Li, Y., Cardei, M., Huang, Y. (eds) Combinatorial Optimization and Applications. COCOA 2019. Lecture Notes in Computer Science(), vol 11949. Springer, Cham. https://doi.org/10.1007/978-3-030-36412-0_33
Download citation
DOI: https://doi.org/10.1007/978-3-030-36412-0_33
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-36411-3
Online ISBN: 978-3-030-36412-0
eBook Packages: Computer ScienceComputer Science (R0)