CO 2018 - Special Session on On the borderline between Data Analysis and Combinatorial Optimisation: models, algorithms, and bounds

Organizers:
Prof. Alexander Kelmanov, Sobolev Institute of Mathematics, Novosibirsk, Russia
Prof. Michael Khachay, Krasovsky Institute of Mathematics and Mechanics, Ekaterinburg, Russia
Description:
Combinatorial optimization and data analysis appear to be extremely close fields of the modern computer science. For instance, various areas in machine learning: PAC-learning, boosting, cluster analysis, feature and model selection, etc. are continuously presenting new challenges for designers of optimization methods due to the steadily increasing demands on accuracy, efficiency, space and time complexity and so on. In many cases, learning problem can be successfully reduced to the appropriate combinatorial optimization problem: max-cut, k-means, p-median, TSP, and so on. To this end, all the results obtained for the latter problem (approximation algorithms, polynomial-time approximation schemes, approximation thresholds) can find their application in design the high-precision and efficient learning algorithms for the former one. On the other hand, there are known examples, where combinatorial optimisation and computational geometry benefits from using approaches developed in statistical learning theory. Among them are Chernoff like measure concentration theorems employed for designing of randomised algorithms and schemas and Bronnimann-Goodrich epsilon-net approach to approximation the famous Hitting Set problem. This session welcomes papers presenting new results on computational and parametric complexity, design and implementation of efficient algorithms and schemes for various extremal problems coming from combinatorial optimisation, classification, clustering, computational geometry, and so on.
Topics of interest include but are not limited to:
computational and parametric complexity
inapproximability issues and approximation thresholds
polynomial time solvable subclasses of intractable problems
polynomial time approximation algorithms and schemes
randomized approximation and asymptotically optimal algorithms
efficient approximation algorithms for geometric settings of NP-hard problems
efficient techniques of supervised, semi-supervised, and unsupervised learning