For a set S of vertices of a graph G, we define its density 0 łeq \sigma(S) łeq 1 as the ratio of the number of edges of G spanned by the vertices of S to \binom|S|2. We show that, given a graph G with n vertices and an integer m łl n, the partition function \sum_S \exp\ \gamma m \sigma(S) \, where the sum is taken over all m-subsets S of vertices and 0 < \gamma <1 is fixed in advance, can be approximated within relative error 0 < \epsilon < 1 in quasi-polynomial n^O(łn m - łn \epsilon) time. We discuss numerical experiments and observe that for the random graph G(n, 1/2) one can afford a much larger \gamma, provided the ratio n/m is sufficiently large.

We consider the traveling salesman problem when the cities are points in ℝ d for some fixed d and distances are computed according to geometric distances, determined by some norm. We show that for any polyhedral norm, the problem of finding a tour of maximum length can be solved in polynomial time. If arithmetic operations are assumed to take unit time, our algorithms run in time O ( n f -2 log n ), where f is the number of facets of the polyhedron determining the polyhedral norm. Thus, for example, we have O ( n 2 log n ) algorithms for the cases of points in the plane under the Rectilinear and Sup norms. This is in contrast to the fact that finding a minimum length tour in each case is NP-hard. Our approach can be extended to the more general case of quasi-norms with a not necessarily symmetric unit ball, where we get a complexity of O ( n 2 f -2 log n ).For the special case of two-dimensional metrics with f = 4 (which includes the Rectilinear and Sup norms), we present a simple algorithm with O ( n ) running time. The algorithm does not use any indirect addressing, so its running time remains valid even in comparison based models in which sorting requires Ω( n log n ) time. The basic mechanism of the algorithm provides some intuition on why polyhedral norms allow fast algorithms.Complementing the results on simplicity for polyhedral norms, we prove that, for the case of Euclidean distances in ℝ d for d ≥ 3, the Maximum TSP is NP-hard. This sheds new light on the well-studied difficulties of Euclidean distances.

We consider the average case behavior of a linear optimization problem on various series of combinatorially interesting polytopes. From general results of integral geometry it follows that for all but an asymptotically negligible fraction of linear functions a polytope can be replaced by a pair of concentric balls with asymptotically equal radii so that the optimal value of the linear function on the polytope is in the interval between the optimal values of the linear function on these balls. In particular, we show that the average case behavior of the assignment problem, traveling salesman problem, and, generally speaking, of any optimization problem on a polynomial fraction of all permutations is the same.

We prove that for any dimension d there exists a polynomial time algorithm for counting integral points in polyhedra in the d-dimensional Euclidean space. Previously such algorithms were known for dimensions d=1,2,3, and 4 only.>

We design polynomial-time algorithms for some particular cases of the volume computation problem and the integral points counting problem for convex polytopes. The basic idea is a reduction to the computation of certain exponential sums and integrals. We give elementary proofs of some known identities between these sums and integrals and prove some new identities.

We consider the problem of deciding whether a given system of quadratic homogeneous equations over the reals has non-trivial solution. We design an approximative algorithm whose complexity is polynomial in the number of variables and exponential in the number of equations. Some applications to general systems of polynomial equations and inequalities over the reals are discussed.