Quick search
Go!

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

Issue:

SSRSMI, Number 2, Volume XIX

Section:

Volume 19, Number 2

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.

Code [ID]:

SSRSMI200902V19S01A0042 [0003154]

Full paper:

Download pdf


Copyright (c) 1995-2007 University of BacŃu