A subexponential algorithm for the coloured tree partition problem

Given a tree of n vertices and a list of feasible colours for each vertex, the coloured tree partition problem (CTPP) consists in partitioning the tree into p vertex-disjoint subtrees of minimum total cost, and assigning to each subtree a different colour, which must be feasible for all of its vertices. The problem is strongly NP-hard on general graphs, as well as on grid and bipartite graphs. This paper deals with the previously open case of tree graphs, showing that it is strongly NP-complete to determine whether a feasible solution exists. It presents reduction, decomposition and bounding procedures to simplify the problem and an exact algorithm of complexity (with ) for the special case in which a vertex of each subtree is given.     

An approximate max-flow min-cut relation for undirected multicommodity flow,with applications

In this paper, we prove the first approximate max-flow min-cut theorem for undirected multicommodity flow. We show that for a feasible flow to exist in a multicommodity problem, it is sufficient that every cut's capacity exceeds its demand by a factor ofO(logClogD), whereC is the sum of all finite capacities andD is the sum of demands. Moreover, our theorem yields an algorithm for finding a cut that is approximately minimumrelative to the flow that must cross it. We use this result to obtain an approximation algorithm for T. C. Hu's generalization of the multiway-cut problem. This algorithm can in turn be applied to obtain approximation algorithms for minimum deletion of clauses of a 2-CNF formula, via minimization, and other problems. We also generalize the theorem to hypergraph networks; using this generalization, we can handle CNF clauses with an arbitrary number of literals per clause.Most of the results in this paper were presented in preliminary form in Approximation through multicommodity flow,Proceedings, 31th Annual Symposium on Foundations of Computer Science (1990), pp. 726–737.Research supported by the National Science Foundation under NSF grant CDA 8722809, by the Office of Naval and the Defense Advanced Research Projects Agency under contract N00014-83-K-0146, and ARPA Order No. 6320, Amendament 1.Research supported by NSF grant CCR-9012357 and by an NSF Presidential Young Investigator Award.     

Asymptotic behaviour of a family of gradient algorithms in ℝ d and Hilbert spaces

The asymptotic behaviour of a family of gradient algorithms (including the methods of steepest descent and minimum residues) for the optimisation of bounded quadratic operators in ℝ^d and Hilbert spaces is analyzed. The results obtained generalize those of Akaike (1959) in several directions. First, all algorithms in the family are shown to have the same asymptotic behaviour (convergence to a two-point attractor), which implies in particular that they have similar asymptotic convergence rates. Second, the analysis also covers the Hilbert space case. A detailed analysis of the stability property of the attractor is provided.     

Deciding uniqueness in norm maximization

NP-hardness is established for the problem whose instance is a system of linear inequalities defining a polytopeP, and whose question is whether, onP, the global maximum of the Euclidean norm is attained at more than one vertex ofP. The NP-hardness persists even for the restricted problem in whichP is a full-dimensional parallelotope with one vertex at the origin. This makes it possible to establish NP-hardness for other uniqueness problems, including some from pseudoboolean programming and computational convexity.Research of the first author was supported in part by the Deutsche Forschungsgemeinschaft. Research of the second author was supported in part by the National Science Foundation.     

An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints

In this paper, we consider combinatorial optimization problems with additional cardinality constraints. In k-cardinality combinatorial optimization problems, a cardinality constraint requires feasible solutions to contain exactly k elements of a finite set E. Problems of this type have applications in many areas, e.g. in the mining and oil industry, telecommunications, circuit layout, and location planning. We formally define the problem, mention some examples and summarize general results. We provide an annotated bibliography of combinatorial optimization problems of which versions with cardinality constraint have been considered in the literature.     

The ellipsoid method and its consequences in combinatorial optimization

L. G. Khachiyan recently published a polynomial algorithm to check feasibility of a system of linear inequalities. The method is an adaptation of an algorithm proposed by Shor for non-linear optimization problems. In this paper we show that the method also yields interesting results in combinatorial optimization. Thus it yields polynomial algorithms for vertex packing in perfect graphs; for the matching and matroid intersection problems; for optimum covering of directed cuts of a digraph; for the minimum value of a submodular set function; and for other important combinatorial problems. On the negative side, it yields a proof that weighted fractional chromatic number is NP-hard. Research by the third author was supported by the Netherlands Organisation for the Advancement of Pure Research (Z.W.O.).     

An Approximation Scheme For Cake Division With A Linear Number Of Cuts

In the cake cutting problem, n≥2 players want to cut a cake into n pieces so that every player gets a ‘fair’ share of the cake by his own measure. We prove the following result: For every ε>0, there exists a cake division scheme for n players that uses at most c_εn cuts, and in which each player can enforce to get a share of at least (1-ε)/n of the cake according to his own private measure. * Partially supported by Institute for Theoretical Computer Science, Prague (project LN00A056 of MŠMT ČR) and grant IAA1019401 of GA AV ČR.     

The complexity of computing the tutte polynomial on transversal matroids

The complexity of computing the Tutte polynomialT(M,x,y) is determined for transversal matroidM and algebraic numbersx andy. It is shown that for fixedx andy the problem of computingT(M,x,y) forM a transversal matroid is #P-complete unless the numbersx andy satisfy (x−1)(y−1)=1, in which case it is polynomial-time computable. In particular, the problem of counting bases in a transversal matroid, and of counting various types of “matchable” sets of nodes in a bipartite graph, is #P-complete.     

Mutual exclusion scheduling with interval graphs or related classes. Part II

This paper is the second part of a study devoted to the mutual exclusion scheduling problem. Given a simple and undirected graph G and an integer k, the problem is to find a minimum coloring of G such that each color is used at most k times. The cardinality of such a coloring is denoted by χ(G,k). When restricted to interval graphs or related classes like circular-arc graphs and tolerance graphs, the problem has some applications in workforce planning. Unfortunately, the problem is shown to be NP-hard for interval graphs, even if k is a constant greater than or equal to four [H.L. Bodlaender, K. Jansen, Restrictions of graph partition problems. Part I. Theoret. Comput. Sci. 148 (1995) 93-109]. In this paper, the problem is approached from a different point of view by studying a non-trivial and practical sufficient condition for optimality. In particular, the following proposition is demonstrated: if an interval graph G admits a coloring such that each color appears at least k times, then χ(G,k)=⌈n/k⌉. This proposition is extended to several classes of graphs related to interval graphs. Moreover, all our proofs are constructive and provide efficient algorithms to solve the MES problem for these graphs, given a coloring satisfying the condition in input.     

Complexity of the Frobenius problem

Consider the Frobenius Problem: Given positive integersa ₁,...,a _n witha _i 2 and such that their greatest common divisor is one, find the largest natural number that is not expressible as a non-negative integer combination ofa ₁,...,a _n. In this paper we prove that the Frobenius problem is NP-hard, under Turing reductions.     

Principal minors, Part I: A method for computing all the principal minors of a matrix

An order O(2ⁿ) algorithm for computing all the principal minors of an arbitrary n × n complex matrix is motivated and presented, offering an improvement by a factor of n³ over direct computation. The algorithm uses recursive Schur complementation and submatrix extraction, storing the answer in a binary order. An implementation of the algorithm in MATLAB® is also given and practical considerations are discussed and treated accordingly.     

A simulation tool for the performance evaluation of parallel branch and bound algorithms

Parallel computation offers a challenging opportunity to speed up the time consuming enumerative procedures that are necessary to solve hard combinatorial problems. Theoretical analysis of such a parallel branch and bound algorithm is very hard and empirical analysis is not straightforward because the performance of a parallel algorithm cannot be evaluated simply by executing the algorithm on a few parallel systems. Among the difficulties encountered are the noise produced by other users on the system, the limited variation in parallelism (the number of processors in the system is strictly bounded) and the waste of resources involved: most of the time, the outcomes of all computations are already known and the only issue of interest is when these outcomes are produced.We will describe a way to simulate the execution of parallel branch and bound algorithms on arbitrary parallel systems in such a way that the memory and cpu requirements are very reasonable. The use of simulation has only minor consequences for the formulation of the algorithm.     

Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra

We present a unifying framework to establish a lower bound on the number of semidefinite-programming-based lift-and-project iterations (rank) for computing the convex hull of the feasible solutions of various combinatorial optimization problems. This framework is based on the maps which are commutative with the lift-and-project operators. Some special commutative maps were originally observed by Lovász and Schrijver and have been used usually implicitly in the previous lower-bound analyses. In this paper, we formalize the lift-and-project commutative maps and propose a general framework for lower-bound analysis, in which we can recapture many of the previous lower-bound results on the lift-and-project ranks.     

Corrigendum to our paper “the ellipsoid method and its consequences in combinatorial optimization”

An error in the proof, and in the statement of a generalization, of the result that submodular setfunctions can be minimized over the subsets with odd cardinality is corrected.     

NOTE ON INVERSE PROBLEM WITH l∞ OBJECTIVE FUNCTION

In this note, the author proves that the inverse problem of submodular function on digraphs with l∞ objective function can be solved by strongly polynomial algorithm. The result shows that most inverse network optimization problems with l∞ objective function can be solved in the polynomial time.     

Computational complexity of inner and outerj-radii of polytopes in finite-dimensional normed spaces

This paper studies the complexity of computing (or approximating, or bounding) the various inner and outer radii of ann-dimensional convex polytope in the space ⁿ equipped with an _p norm or a polytopal norm. The polytopeP is assumed to be presented as the convex hull of finitely many points with rational coordinates (V-presented) or as the intersection of finitely many closed halfspaces defined by linear inequalities with rational coefficients (-presented). The innerj-radius ofP is the radius of a largestj-ball contained inP; it isP's inradius whenj = n and half ofP's diameter whenj = 1. The outerj-radius measures how wellP can be approximated, in a minimax sense, by an (n — j)-flat; it isP's circumradius whenj = n and half ofP's width whenj = 1. The binary (Turing machine) model of computation is employed. The primary concern is not with finding optimal algorithms, but with establishing polynomial-time computability or NP-hardness. Special attention is paid to the case in whichP is centrally symmetric. When the dimensionn is permitted to vary, the situation is roughly as follows: (a) for general -presented polytopes in _p spaces with 1相似文献   

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.     

Fixed point optimization algorithm and its application to network bandwidth allocation

A convex optimization problem for a strictly convex objective function over the fixed point set of a nonexpansive mapping includes a network bandwidth allocation problem, which is one of the central issues in modern communication networks. We devised an iterative algorithm, called a fixed point optimization algorithm, for solving the convex optimization problem and conducted a convergence analysis on the algorithm. The analysis guarantees that the algorithm, with slowly diminishing step-size sequences, weakly converges to a unique solution to the problem. Moreover, we apply the proposed algorithm to a network bandwidth allocation problem and show its effectiveness.