On the complexity and approximability of some Euclidean optimal summing problems

The complexity status of several well-known discrete optimization problems with the direction of optimization switching from maximum to minimum is analyzed. The task is to find a subset of a finite set of Euclidean points (vectors). In these problems, the objective functions depend either only on the norm of the sum of the elements from the subset or on this norm and the cardinality of the subset. It is proved that, if the dimension of the space is a part of the input, then all these problems are strongly NP-hard. Additionally, it is shown that, if the space dimension is fixed, then all the problems are NP-hard even for dimension 2 (on a plane) and there are no approximation algorithms with a guaranteed accuracy bound for them unless P = NP. It is shown that, if the coordinates of the input points are integer, then all the problems can be solved in pseudopolynomial time in the case of a fixed space dimension.     

On the complexity of some quadratic Euclidean 2-clustering problems

Some problems of partitioning a finite set of points of Euclidean space into two clusters are considered. In these problems, the following criteria are minimized: (1) the sum over both clusters of the sums of squared pairwise distances between the elements of the cluster and (2) the sum of the (multiplied by the cardinalities of the clusters) sums of squared distances from the elements of the cluster to its geometric center, where the geometric center (or centroid) of a cluster is defined as the mean value of the elements in that cluster. Additionally, another problem close to (2) is considered, where the desired center of one of the clusters is given as input, while the center of the other cluster is unknown (is the variable to be optimized) as in problem (2). Two variants of the problems are analyzed, in which the cardinalities of the clusters are (1) parts of the input or (2) optimization variables. It is proved that all the considered problems are strongly NP-hard and that, in general, there is no fully polynomial-time approximation scheme for them (unless P = NP).     

On the complexity of some Euclidean problems of partitioning a finite set of points

Problems of partitioning a finite set of Euclidean points (vectors) into clusters are considered. The criterion is to minimize the sum, over all clusters, of (1) squared norms of the sums of cluster elements normalized by the cardinality, (2) squared norms of the sums of cluster elements, and (3) norms of the sum of cluster elements. It is proved that all these problems are strongly NP-hard if the number of clusters is a part of the input and are NP-hard in the ordinary sense if the number of clusters is not a part of the input (is fixed). Moreover, the problems are NP-hard even in the case of dimension 1 (on a line).     

On the complexity of some subgraph problems

We study the complexity of the problem of deciding the existence of a spanning subgraph of a given graph, and of that of finding a maximum (weight) such subgraph. We establish some general relations between these problems, and we use these relations to obtain new NP-completeness results for maximum (weight) spanning subgraph problems from analogous results for existence problems and from results in extremal graph theory. On the positive side, we provide a decomposition method for the maximum (weight) spanning chordal subgraph problem that can be used, e.g., to obtain a linear (or O(nlogn)) time algorithm for such problems in graphs with vertex degree bounded by 3.     

On the complexity of some data analysis problems

NP-completeness of certain discrete optimization problems is proved. These are the problems to which one can reduce some important problems arising in data analysis when certain subsets of vectors are sought.     

On the complexity of some cluster analysis problems

NP-completeness of certain important clusterization problems for a finite set of vectors is proved.     

On complexity of optimal recombination for flowshop scheduling problems

Under study is the complexity of optimal recombination for various flowshop scheduling problems with the makespan criterion and the criterion of maximum lateness. The problems are proved to be NP-hard, and a solution algorithm is proposed. In the case of a flowshop problem on permutations, the algorithm is shown to have polynomial complexity for “almost all” pairs of parent solutions as the number of jobs tends to infinity.     

On the complexity of some problems related to graph extensions

The computational complexity of problems related to the construction of k-extensions of graphs is studied. It is proved that the problems of recognizing vertex and edge k-extensions are NP-complete. The complexity of recognizing irreducible, minimal, and exact vertex and edge k-extensions is considered.     

On the empirical time complexity of finding optimal solutions vs proving optimality for Euclidean TSP instances

We investigate the empirical performance of the long-standing state-of-the-art exact TSP solver Concorde on various classes of Euclidean TSP instances and show that, surprisingly, the time spent until the first optimal solution is found accounts for a large fraction of Concorde’s overall running time. This finding holds for the widely studied random uniform Euclidean (RUE) instances as well as for several other widely studied sets of Euclidean TSP instances. On RUE instances, the median fraction of Concorde’s total running time spent until an optimal solution is found ranges from 0.77 for \(n=500\) to 0.97 for \(n=3{,}500\); on TSPLIB, National and VLSI instances, we pegged it at 0.86, 0.74 and 0.61, respectively, with a tendency of even smaller values for larger instances.     

On summing permutations and some statistical properties

A closed form expression is obtained for the sum of all permutations of n objects taken r at a time. The average and variance of the permutations are derived and are shown to be proportional to the average and variance of the objects themselves. The proportionality constant is a function of only r, n and the base b and is independent of the actual objects considered. Previous results aimed at determining the sum of permutations are shown to be very specific cases of the current development.     

On some optimal control problems connected with the Navier-Stokes system

We consider problems of the form $$\left\{ \begin{gathered} J(y) \to \inf : \hfill \\ L(y) = u, \left\| u \right\| \leqslant M, y(0) = 0, y(T) = v, \hfill \\\end{gathered} \right.$$ whereL is the operator of the Navier-Stokes system. We obtain theorems for existence of a solution and necessary and sufficient conditions for an extremum. We also study the uniqueness of the solution and construct the asymptotics of the solution in terms of the parameter M. Bibliography: 11 titles.     

On complexity of some problems of cluster analysis of vector sequences

NP-completeness of two clustering (partition) problems is proved for a finite sequence of Euclidean vectors. In the optimization versions of both problems it is required to partition the elements of the sequence into a fixed number of clusters minimizing the sum of squares of the distances from the cluster elements to their centers. In the first problem the sizes of clusters are the part of input, while in the second they are unknown (they are the variables for optimization). Except for the center of one (special) cluster, the center of each cluster is the mean value of all vectors contained in it. The center of the special cluster is zero. Also, the partition must satisfy the following condition: The difference between the indices of two consecutive vectors in every nonspecial cluster is bounded below and above by two given constants.     

On minimizing the conditional entropy for some problems of optimal diagnosis

For the diagnosis of damage processes in engineering it may be important to determine the present state of a technical system from indirectmeasurements. In this paper, we consider specific optimization aspects of this inverse problem based on a traditional approach of Bayesian classification. There are formulated criteria of optimal diagnosis in the case of scalar observation values (diagnostic numbers). We focus ourattention to the optimal choice of a fixed number of diagnosis intervals by minimizing the conditional entropy. It is shown that under weak assumptions the associated nonlinear optimization problems with monotonicity constraints become well-posed. We discuss properties of optimal solutions and their asymptotic behavic~ra s the number of diagnosis classes tends to infinity. Moreover, a heuristically motivated algorithm for the iterative solution of these extremal problems will be suggested. The paper is completed by a numerical case study based on a tutorial example for Gaussian distributions.     

On some elliptic optimal control problems with state constraints

In this paper optimality conditions will be derived for elliptic optimal control problems with a restriction on the state or on the gradient of the state. Essential tools are the method of transposition and generalized trace theorems and green's formulas from the theory of elliptic differential equations.     

On the complexity of some arborescences finding problems on a multihop radio network

An arborescence of a multihop radio network is a directed spanning tree (with rootx) such that the edges are directed away from the root. Based upon an arborescence,x canbroadcast a message to other nodes according to the directed edges of the spanning tree. The minimum transmission power arborescence problem is to find an arborescence such that the message can be broadcasted to other nodes by using a minimal amount of transmission power. The minimum delay arborescence problem is to find an arborescence such that a message can be broadcasted to other nodes by using a minimal number of broadcast transmission. In this paper we show that both these problems areNP-complete. The reductions are from the maximum leaf spanning tree problem.Areverse arborescence is similar to an arborescence except that the edges are directed toward the root. Based upon a reverse arborescence, the root node cancollect information from other nodes. In this paper we also show that the reverse minimum transmission power arborescence problem can be solved with the same computational complexity as that of finding a minimum cost spanning tree, and the reverse minimum delay arborescence problem can be solved with the same computational complexity as that of finding a spanning tree.