UDC 519.85
1 V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine
 stetsyukp@gmail.com
|
2 V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine
khomiak.olha@gmail.com
|
|
|
4 V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine
anton_s2007@ukr.net
|
OPTIMIZATION PROBLEMS FOR THE MAXIMUM k-PLEX
Abstract. A quadratic optimization problem for finding the maximum
k-plex in an undirected graph is constructed. Two families of superfluous quadratic constraints are presented,
which are obtained by means of constraints of the Boolean linear programming problem for the maximum k-plex.
The influence of superfluous constraints on the improvement of the accuracy of Lagrangian dual bounds
for the objective function of the quadratic problem is investigated. An algorithm for searching
all the maximum k-plexes is developed and the results of test experiments for its implementation using
the GLPK software package (GNU Linear Programming Kit) are presented.
Keywords: maximum k-plex, maximum clique, quadratic optimization problem, Boolean linear programming problem,
superfluous constraint, Lagrangian dual bound.
FULL TEXT
REFERENCES
- Seidman S.B., Foster B.L. A graph theoretic generalization of the clique concept. J. of Math. Sociology. 1978. Vol. 6. P. 139–154.
- Balansundaram B., Butenko S., Hicks I.V. Clique relaxations in social network analysis: The maximum k-plex problem. Operations Research. 2011. Vol. 59, N 1. P. 133–142.
- Guo J., Komusiewicz C., Niedermeier R., Uhlmann J. A more relaxed model for graph-based data clustering: s-plex cluster editing. SIAM J. Discrete Math. 2010. Vol. 24, N 4. P. 1662–1683.
- McClosky B., Hicks I.V. Combinatorial algorithms for the maximum k-plex problem. J. of Combinatorial Optimization. 2012. Vol. 23, N 1. P. 29–49.
- Pattillo J., Veremyev A., Butenko S., Boginski V. On the maximum quasi-clique problem. Discrete Applied Mathematics. 2013. Vol. 161, N 1–2. P. 244–257.
- Stetsyuk P.I., Bardadim T.O., Lyashko V.I. A quadratic problem for a maximal k-plex in an undirected graph. Zhurnal obchyslyuvalʹnoyi ta prykladnoyi matematyky. 2017. N 1 (124). P. 80–87.
- Stetsyuk P.I., Lyashko V.I., Bardadym T.O. Properties of the quadratic problem on the maximum k-plex in an undirected graph. Scientific notes of NaUKMA. Computer Science. 2017. Vol. 198, N 1(124). P. 80–87.
- Stetsyuk PI, Khomyak OM Use the GLPK package to find all solutions to the -plex problem. Proceedings of the XXIII International Scientific and Practical Seminar named after A.Ya. Petrenyuk "Combinatorial configurations and their applications", dedicated to the 70th anniversary of the Flight Academy of the National Aviation University (May 13-15, 2021, Zaporizhzhya-Kropyvnytskyi, Ukraine). Zaporizhzhia – Kropyvnytskyi, 2021. Kropyvnytskyi: PE “Exclusive-Systems”, 2021. P. 174–179.
- Shor N.Z. Nondifferentiable optimization and polynomial problems. London; Boston; Dordrecht: Kluwer Academic Publishers, 1998. 394 p.
- Stetsyuk P.I. Dual estimates in quadratic extremal problems [in Russian]. Chisinau: Eureka, 2018. 504 p.
- Shor N.Z., Stetsyuk P.I. Dual solution of quadratic-type problems by -algorithm (subroutine DSQTPr). Abstracts of the Second International Workshop “Recent Advances in Non-Differentiable Optimization” (1–4 October, 2001, Kyiv, Ukraine). Kyiv, 2001. P. 36.
- Eaton J.W., Bateman D., Hauberg S. GNU Octave Manual Version 3. Network Theory Ltd, 2008. 568 p.
- Stetsyuk P.I. On Functionally redundant constraints for Boolean optimization problems of quadratic type. Kibernetika i sistemnyj analiz. 2005. Vol. 41, N 6. P. 168–171.
- Stetsyuk P.I. New models of quadratic type for the problem of the maximum weighted cut of a graph. Kibernetika i sistemnyj analiz. 2006. Vol. 42, N 1. P. 63––75.
