Co-author(s) :

Aslanyan Levon ; Sahakyan Hasmik

Abstract:

This article, in general, is devoted to a set of discrete optimization issues derived from the domain of pattern recognition, machine learning and data mining - specifically. The global objectives are the compactness hypotheses of pattern recognition, and the structural reconstruction of the discrete tomography. The driving force of the current research was the proof technic of the discrete isoperimetry problem. In proofs by induction the split technique was applied and then it is important to have some information about the sizes of the split compounds. Isoperimetry itself is a formalism of the compactness hypotheses. From one side knowledge on split sizes helps to find the compact structures and learning sets based on this, from the other side – split sizes help to prove the necessary relations. The pure combinatorial approaches are not able at the moment to give an efficient description of the split sizes and – the weighted row-different matrices. The probabilistic method, as it is well-known, gives additional knowledge about the random subsets, and this may be useful as a complementary knowledge about a different objects or a situations concerned the properties of discrete structures – isoperimetry and tomography. The discrete mathematical science deals with different types of discrete structures, studying their transformations and properties. In some problems we face the issues about the existence of structures under some special constraints, about the enumeration of structures under these constraints, and – on algorithmic optimization. Given a simple structure – in some cases, it can be even hard to compute some basic properties of it. Such are for example the graph chromatic number, the minimal set cover, the solution of the well-known SAT and plenty of other NP-complete problems. When structures are given, the mentioned parameters may be easily computable. To find a structure by the given parameters often becomes hard. We call such problems – inverse problems. Our special interest is in considering of simple (0,1) matrices and their row and column weights. Given a matrix we can compute the mentioned weights (direct problem). The inverse problem, -- when it is to find the construction with the given weights is not simple. At least there is not known polynomial algorithms for this problem. Moreover, the problem is known as the hypotheses posted by famous graph theorist C. Berge so that the problem is well known and unsolved. Besides the logical and combinatorial analysis of the inverse type problems of discrete optimization, in several cases the probabilistic models were applied successfully. The idea of this paper is to use the probabilistic theory of combinatorial analysis to the discrete tomography problem given in terms of the (0,1) matrices. The paper tries to outline the models, relations and the methodology. Our research priority interest is to understand the opportunities, similarities and perspectives in this broad research area. The study is ongoing and the follow up publication will come soon.

Publisher:

ITHEA

Date of publication:

2016

Identifier:

oai:noad.sci.am:135912

ISSN:

1310-0513

Language:

English

Journal or Publication Title:

International Journal Information Theories and Applications

Volume:

23

Number:

3

URL:

Affiliation:

Institute for Informatics and Automation Problems

Country:

Armenia