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.

Keywords

Recognition algorithm polar graph weakly decomposition time-series clustering data-mining