<Emphasis Type="Bold">NP</Emphasis> -Hardness of Largest Contained and Smallest Containing Simplices for <Emphasis Type="Italic">V</Emphasis>- and <Emphasis Type="Italic">H</Emphasis>-Polytopes

   Abstract. The problem of finding a d -simplex of maximum volume in an arbitrary d -dimensional V -polytope, for arbitrary d , was shown by Gritzmann et al. [GKL] in 1995 to be NP-hard. They conjectured that the corresponding problem for H -polytopes is also NP-hard. This paper presents a unified way of proving the NP-hardness of both these problems. The approach also yields NP-hardness proofs for the problems of finding d -simplices of minimum volume containing d -dimensional V - or H -polytopes. The polytopes that play the key role in the hardness proofs are truncations of simplices. A construction is presented which associates a truncated simplex to a given directed graph, and the hardness results follow from the hardness of detecting whether a directed graph has a partition into directed triangles.     

NP -Hardness of Largest Contained and Smallest Containing Simplices for V - and H -Polytopes

Abstract. The problem of finding a d -simplex of maximum volume in an arbitrary d -dimensional V -polytope, for arbitrary d , was shown by Gritzmann et al. [GKL] in 1995 to be NP-hard. They conjectured that the corresponding problem for H -polytopes is also NP-hard. This paper presents a unified way of proving the NP-hardness of both these problems. The approach also yields NP-hardness proofs for the problems of finding d -simplices of minimum volume containing d -dimensional V - or H -polytopes. The polytopes that play the key role in the hardness proofs are truncations of simplices. A construction is presented which associates a truncated simplex to a given directed graph, and the hardness results follow from the hardness of detecting whether a directed graph has a partition into directed triangles.     

Volumes of complementary projections of convex polytopes

The centrally symmetric convex polytopes whose images under orthogonal projection on to any pair of orthogonal complementary subspaces ofE ^d have numerically equal volumes are shown hare to be certain cartesian products of polygons and line segments. Ford3, the general projection property in fact follows from that for pairs of hyperplanes and lines. A conjecture is made about the problem in the non-centrally symmetric case.     

Computational complexity of norm-maximization

This paper discusses the problem of maximizing a quasiconvex function over a convex polytopeP inn-space that is presented as the intersection of a finite number of halfspaces. The problem is known to beNP-hard (for variablen) when is thep ^th power of the classicalp-norm. The present reexamination of the problem establishesNP-hardness for a wider class of functions, and for thep-norm it proves theNP-hardness of maximization overn-dimensionalparallelotopes that are centered at the origin or have a vertex there. This in turn implies theNP-hardness of {–1, 1}-maximization and {0, 1}-maximization of a positive definite quadratic form. On the good side, there is an efficient algorithm for maximizing the Euclidean norm over an arbitraryrectangular parallelotope.The authors are indebted to J. O'Rourke, P, Pardalos and R. Freund for useful references. The second and third authors are indebted to the Institute for Mathematics and its Applications in Minneapolis, where much of this paper was written: they acknowledge additional support from the Alexander von Humboldt Stiftung and the National Science Foundation, respectively.     

Projection theorems in hyperbolic space

We establish Marstrand-type projection theorems for orthogonal projections along geodesics onto m-dimensional subspaces of the hyperbolic n-space by a geometric argument. Moreover, we obtain a Besicovitch–Federer type characterization of purely unrectifiable sets in terms of these hyperbolic orthogonal projections.

     

Edge cover by connected bipartite subgraphs

We consider the problem of covering the edge set of an unweighted, undirected graph with the minimum number of connected bipartite subgraphs (where the subgraphs are not necessarily bicliques). We show that this is an NP-hard problem, provide lower bounds through an integer programming formulation, propose several constructive heuristics and a local search, and discuss computational results. Finally, we consider a constrained variant of the problem which we show to be NP-hard, and provide an integer programming formulation for the variant.     

Inverse <Emphasis Type="Italic">p</Emphasis>-median problems with variable edge lengths

The inverse p-median problem with variable edge lengths on graphs is to modify the edge lengths at minimum total cost with respect to given modification bounds such that a prespecified set of p vertices becomes a p-median with respect to the new edge lengths. The problem is shown to be strongly NP{\mathcal{NP}}-hard on general graphs and weakly NP{\mathcal{NP}}-hard on series-parallel graphs. Therefore, the special case on a tree is considered: It is shown that the inverse 2-median problem with variable edge lengths on trees is solvable in polynomial time. For the special case of a star graph we suggest a linear time algorithm.     

Cutting hyperplanes for divide-and-conquer

Givenn hyperplanes inE ^d, a (1/r)-cutting is a collection of simplices with disjoint interiors, which together coverE ^d and such that the interior of each simplex intersects at mostn/r hyperplanes. We present a deterministic algorithm for computing a (1/r)-cutting ofO(r ^d) size inO(nr ^d–1) time. If we require the incidences between the hyperplanes and the simplices of the cutting to be provided, then the algorithm is optimal. Our method is based on a hierarchical construction of cuttings, which also provides a simple optimal data structure for locating a point in an arrangement of hyperplanes. We mention several other applications of our result, e.g., counting segment intersections, Hopcroft's line/point incidence problem, linear programming in fixed dimension.This research was supported in part by the National Science Foundation under Grant CCR-9002352.     

On the Computational Complexity of the Minimum Committee Problem

Two special cases of the Minimum Committee Problem are studied, the Minimum Committee Problem of Finite Sets (MCFS) and the Minimum Committee Problem of a System of Linear Inequalities(MCLE). It is known that the first of these problems is NP-hard (see (Mazurov et al., Proc. Steklov Inst. Math., 1:67–101, 2002)). In this paper we show the NP-hardness of two integer optimization problems connected with it. In addition, we analyze the hardness of approximation to the MCFS problem. In particular, we show that, unless NP⊂TIME(n ^O(loglogn )), for every ε>0 there are no approximation algorithms for this problem with approximation ratio (1–ε)ln (m–1), where m is the number of inclusions in the MCFS problem. To prove this bound we use the SET COVER problem, for which a similar result is known (Feige, J. ACM, 45:634–652, 1998). We also show that the Minimum Committee of Linear Inequalities System (MCLE) problem is NP-hard as well and consider an approximation algorithm for this problem.      

Special bases for solutions of a generalized Maxwell system in 3‐dimensional space

The aim of this paper is to study complete polynomial systems in the kernel space of conformally invariant differential operators in higher spin theory. We investigate the kernel space of a generalized Maxwell operator in 3‐dimensional space. With the already known decomposition of its homogeneous kernel space into 2 subspaces, we investigate first projections from the homogeneous kernel space to each subspace. Then, we provide complete polynomial systems depending on the given inner product for each subspace in the decomposition. More specifically, the complete polynomial system for the homogenous kernel space is an orthogonal system wrt a given Fischer inner product. In the case of the standard inner product in L² on the unit ball, the provided complete polynomial system for the homogeneous kernel space is a partially orthogonal system. Further, if the degree of homogeneity for the respective subspaces in the decomposed kernel spaces approaches infinity, then the angle between the 2 subspaces approaches π/2.     

Inverse median location problems with variable coordinates

Given n points in \mathbbR^d{\mathbb{R}^d} with nonnegative weights, the inverse 1-median problem with variable coordinates consists in changing the coordinates of the given points at minimum cost such that a prespecified point in \mathbbR^d{\mathbb{R}^d} becomes the 1-median. The cost is proportional to the increase or decrease of the corresponding point coordinate. If the distances between points are measured by the rectilinear norm, the inverse 1-median problem is NP{\mathcal{NP}}-hard, but it can be solved in pseudo-polynomial time. Moreover, a fully polynomial time approximation scheme exists in this case. If the point weights are assumed to be equal, the corresponding inverse problem can be reduced to d continuous knapsack problems and is therefore solvable in O(nd) time. In case that the squared Euclidean norm is used, we derive another efficient combinatorial algorithm which solves the problem in O(nd) time. It is also shown that the inverse 1-median problem endowed with the Chebyshev norm in the plane is NP{\mathcal{NP}}-hard. Another pseudo-polynomial algorithm is developed for this case, but it is shown that no fully polynomial time approximation scheme does exist.     

Closed Projections and Peak Interpolation for Operator Algebras

The closed one-sided ideals of a C ^*-algebra are exactly the closed subspaces supported by the orthogonal complement of a closed projection. Let A be a (not necessarily selfadjoint) subalgebra of a unital C ^*-algebra B which contains the unit of B. Here we characterize the right ideals of A with left contractive approximate identity as those subspaces of A supported by the orthogonal complement of a closed projection in B ^** which also lies in . Although this seems quite natural, the proof requires a set of new techniques which may be viewed as a noncommutative version of the subject of peak interpolation from the theory of function spaces. Thus, the right ideals with left approximate identity are closely related to a type of peaking phenomena in the algebra. In this direction, we introduce a class of closed projections which generalizes the notion of a peak set in the theory of uniform algebras to the world of operator algebras and operator spaces.     

Primal and polar approach for computing the symmetric diagonally dominant projection

We solve the problem of minimizing the distance from a given matrix to the cone of symmetric and diagonally dominant matrices with positive diagonal (SDD⁺). Using the extreme rays of the polar cone we project onto the supporting hyperplanes of the faces of SDD⁺ and then, applying the cyclic Dykstra's algorithm, we solve the problem. Similarly, using the extreme rays of SDD⁺ we characterize the projection onto the polar cone, which also allows us to obtain the projection onto SDD⁺ by means of the orthogonal decomposition theorem for convex cones. In both cases the symmetry and the sparsity pattern of the given matrix are preserved. Preliminary numerical experiments indicate that the polar approach is a promising one. Copyright © 2002 John Wiley & Sons, Ltd.     

How to find Nash equilibria with extreme total latency in network congestion games?

We study the complexity of finding extreme pure Nash equilibria in symmetric network congestion games and analyse how it is influenced by the graph topology and the number of users. In our context best and worst equilibria are those with minimum or maximum total latency, respectively. We establish that both problems can be solved by a Greedy type algorithm equipped with a suitable tie breaking rule on extension-parallel graphs. On series-parallel graphs finding a worst Nash equilibrium is NP-hard for two or more users while finding a best one is solvable in polynomial time for two users and NP-hard for three or more. additionally we establish NP-hardness in the strong sense for the problem of finding a worst Nash equilibrium on a general acyclic graph.     

Minimizing the weighted number of tardy jobs with due date assignment and capacity-constrained deliveries

We study a supply chain scheduling problem, where a common due date is assigned to all jobs and the number of jobs in delivery batches is constrained by the batch size. Our goal is to minimize the sum of the weighted number of tardy jobs, the due-date-assignment costs and the batch-delivery costs. We show that some well-known NP\mathcal{NP}-hard problems reduce to our problem. Then we propose a pseudo-polynomial algorithm for the problem, establishing that it is NP\mathcal{NP}-hard only in the ordinary sense. Finally, we convert the algorithm into an efficient fully polynomial time approximation scheme.     

Bin packing: On optimizing the number of pieces packed

We consider bin-packing variations related to the well-studied problem of maximizing the total number of pieces packed into a fixed set of bins. We show that, when the objective is to minimize the total number of pieces packed subject to the constraint that no unpacked piece will fit, no polynomial-time relative approximation algorithm exists (unless, of course,P=NP). That is, we prove that it isNP-hard to guarantee packing no more than a constant multiple of the optimal number of pieces, for any constant. This appears to be the first bin-packing problem for which this property has been demonstrated. Furthermore, this result also holds for the allied packing variant which seeks to minimize the maximum number of pieces packed in any single bin. We find the situation to be markedly better for the problem of maximizing the minimum number of pieces in any bin. If all bins possess the same capacity, we prove that the familiar SPF rule is an absolute approximation algorithm with additive constant 1, and can therefore be regarded as a best possible heuristic. For the more general and difficult case in which bin capacities may differ, it turns out that SPF fails to qualify as even a relative approximation algorithm. However, we devise an implementation of the well-known FFD heuristic, which we show to be a relative approximation algorithm, yielding a worst-case performance ratio of 1/2 with additive constant 0. Moreover, we prove that (unlessP=NP) no polynomial-time algorithm can guarantee a higher ratio without sacrificing the additive constant.This author's research is supported in part by the National Science Foundation under grants ECS-8403859 and MIP-8603879.     

An efficient representation of Benes networks and its applications

The most popular bounded-degree derivative network of the hypercube is the butterfly network. The Benes network consists of back-to-back butterflies. There exist a number of topological representations that are used to describe butterfly—like architectures. We identify a new topological representation of butterfly and Benes networks.The minimum metric dimension problem is to find a minimum set of vertices of a graph G(V,E) such that for every pair of vertices u and v of G, there exists a vertex w with the condition that the length of a shortest path from u to w is different from the length of a shortest path from v to w. It is NP-hard in the general sense. We show that it remains NP-hard for bipartite graphs. The algorithmic complexity status of this NP-hard problem is not known for butterfly and Benes networks, which are subclasses of bipartite graphs. By using the proposed new representations, we solve the minimum metric dimension problem for butterfly and Benes networks. The minimum metric dimension problem is important in areas such as robot navigation in space applications.     

Local and variable neighborhood search for the <Emphasis Type="Italic">k</Emphasis>-cardinality subgraph problem

The minimum weighted k-cardinality subgraph problem consists of finding a connected subgraph of a given graph with exactly k edges whose sum of weights is minimum. For this NP-hard combinatorial problem, only constructive types of heuristics have been suggested in the literature. In this paper we propose a new heuristic based on variable neighborhood search metaheuristic rules. This procedure uses a new local search developed by us. Extensive numerical results that include graphs with up to 5,000 vertices are reported. It appears that VNS outperforms all previous methods.     

Proportional concentration phenomena on the sphere

In this paper we establish concentration phenomena for subspaces with arbitrary dimension. Namely, we display conditions under which the Haar measure on the sphere concentrates on a neighborhood of the intersection of the sphere with a subspace ofR ⁿ of a given dimension. We display applications to a problem of projections of points on the sphere, and to the duality of entropy numbers conjecture. Research was partially supported by the Israel Science Foundation.