Proceedings of ISP RAS


Optimal Ordering of Conflicting Objects and the Traveling Salesman Problem.

Alexey Voevodin, Semen Kosyachenko.

Abstract

The paper presents the setting of the problem of optimal ordering of conflicting objects. This problem appears in sociology, in advertising on TV and other media networks. Point is that positions of some conflicting commercials were as far apart as possible if commercials belong to the same class of goods or the same advertiser or brand. Solution algorithms are described for this and related problems such as the Travelling Salesman Problem (TSP). The tasks are considered of two types: when penalized only a juxtaposition of objects according to the TSP, and the generalized case when the penalty acts on the neighboring and on the distant to each other conflicting objects. The penalty depends on the number of objects that lie between them. The TSP with sparse matrix is also considered. For sparse practice cases of the TSP with the band or block diagonal matrix necessary and sufficient conditions are proved to objective function attained its zero minimum and the algorithms guaranteeing exact solution for the TSP are constructed. The proposed algorithms are effective also for sparse matrices of general type. These algorithms can also be successfully used as approximate algorithms for matrices close to the band or block diagonal. For the general case in the paper we propose a heuristic algorithm with high performance and good accuracy of solution. We got good scalability to any size while maintaining linear complexity, which allowed us to use these proposed algorithms in practice for large amounts of data, such as advertising in media networks. The practical results of analytical and numerical investigations of algorithm complexity and solution accuracy are presented.

Keywords

optimal placement; Travelling Salesman Problem; TSP; NP-hard problems; band matrix; sparse matrix; greedy algorithm; penalty function; conflicts, media network; advertising

Edition

Proceedings of the Institute for System Programming, vol. 25, 2013, pp. 207-224.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2013-25-12

Full text of the paper in pdf (in Russian) Back to the contents of the volume