COMBINATORIAL OPTIMIZATION ALGORITHMS FOR POLAR GRAPHS AND THEIR APPLICATIONS IN FINANCE
D. PACURARI(1), M. MUNTEANU(1), M.TALMACIU(2)
1. Economics Studies Faculty, University of Bacău, Spiru Haret 8, 600114, Bacău, ROMANIA, email: doinap ro@yahoo.com, mircea.muntean.bc@mfinante.ro
2. Faculty of Science, University of Bacău, Spiru Haret 8, 600114, Bacău, ROMANIA, email: mtalmaciu@ub.ro
Abstract
Many natural problems in finance involve partitioning assets into natural groups or identifying assets with similar properties. Building a diversified portfolio is somehow dual to clustering. An approach to clustering constructs an similarity graph, where elements i and j are connected by an edge if and only if i and j are similar that they should/can be in the same cluster. If the similarity measure is totally correct and consistent, the graph will consist of disjoint cliques, one per cluster. A graph is (s, k)-polar if there exists a partition A,B of its vertex set such that A induces a complete s-partite graph and B a disjoint union of at most k cliques. Recognizing a polar graph is known to be NP-complete. In this paper we determine the density and the stability number for (s,k)-polar graphs with algorithms that are comparable, while respect to computing time, with the existing ones and we give some applications in finance.