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 analysis of the greedy algorithm for the submodular set covering problem

We consider the problem: min \(\{ \mathop \Sigma \limits_{j \in s} f_j :z(S) = z(N),S \subseteqq N\} \) wherez is a nondecreasing submodular set function on a finite setN. Whenz is integer-valued andz(Ø)=0, it is shown that the value of a greedy heuristic solution never exceeds the optimal value by more than a factor \(H(\mathop {\max }\limits_j z(\{ j\} ))\) where \(H(d) = \sum\limits_{i = 1}^d {\frac{1}{i}} \) . This generalises earlier results of Dobson and others on the applications of the greedy algorithm to the integer covering problem: min {fy: Ay ≧b, y ε {0, 1}} wherea _ij ,b _i } ≧ 0 are integer, and also includes the problem of finding a minimum weight basis in a matroid.     

More analysis of double hashing

In [8], a deep and elegant analysis shows that double hashing is asymptotically equivalent to the ideal uniform hashing up to a load factor of about 0.319. In this paper we show how a randomization technique can be used to develop a surprisingly simple proof of the result that this equivalence holds for load factors arbitrarily close to 1.An earlier version of the paper was presented at the20th Annual ACM Symposium on Theory of Computing, Chicago, IL, May 1988.Supported by National Science Foundation Grants DCR 85-09667 and CCR 89-12063 at the University of California at IrvinePartially supported by National Science Foundation Grant DCR 85-09667 at the University of California at Irvine     

Adaptive Itô-Taylor algorithm can optimally approximate the Itô integrals of singular functions

We deal with numerical approximation of stochastic Itô integrals of singular functions. We first consider the regular case of integrands belonging to the Hölder class with parameters r and ?. We show that in this case the classical Itô-Taylor algorithm has the optimal error Θ(n^−(r+?)). In the singular case, we consider a class of piecewise regular functions that have continuous derivatives, except for a finite number of unknown singular points. We show that any nonadaptive algorithm cannot efficiently handle such a problem, even in the case of a single singularity. The error of such algorithm is no less than n^{−min{1/2,r+?}}. Therefore, we must turn to adaptive algorithms. We construct the adaptive Itô-Taylor algorithm that, in the case of at most one singularity, has the optimal error O(n^−(r+?)). The best speed of convergence, known for regular functions, is thus preserved. For multiple singularities, we show that any adaptive algorithm has the error Ω(n^{−min{1/2,r+?}}), and this bound is sharp.     

Improved bounds on the max-flow min-cut ratio for multicommodity flows

In this paper we consider the worst case ratio between the capacity of min-cuts and the value of max-flow for multicommodity flow problems. We improve the best known bounds for the min-cut max-flow ratio for multicommodity flows in undirected graphs, by replacing theO(logD) in the bound byO(logk), whereD denotes the sum of all demands, andk demotes the number of commodities. In essence we prove that up to constant factors the worst min-cut max-flow ratios appear in problems where demands are integral and polynomial in the number of commodities.Klein, Rao, Agrawal, and Ravi have previously proved that if the demands and the capacities are integral, then the min-cut max-flow ratio in general undirected graphs is bounded byO(logClogD), whereC denotes the sum of all the capacities. Tragoudas has improved this bound toO(lognlogD), wheren is the number of nodes in the network. Garg, Vazirani and Yannakakis further improved this toO(logklogD). Klein, Plotkin and Rao have proved that for planar networks, the ratio isO(logD).Our result improves the bound for general networks toO(log² k) and the bound for planar networks toO(logk). In both cases our result implies the first non-trivial bound that is independent of the magnitude of the numbers involved. The method presented in this paper can be used to give polynomial time approximation algorithms to the minimum cuts in the network up to the above factors.Preliminary version appeared in Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, 1993, 691-697.Research supported by U.S. Army Research Office Grant DAAL-03-91-G-0102, and by a grant from Mitsubishi Electric Laboratories.Research supported in part by a Packard Fellowship, an NSF PYI award, a Sloan Fellowship, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.     

A new graph triconnectivity algorithm and its parallelization

We present a new algorithm for finding the triconnected components of an undirected graph. The algorithm is based on a method of searching graphs called open ear decomposition. A parallel implementation of the algorithm on a CRCW PRAM runs inO(log² n) parallel time usingO(n+m) processors, wheren is the number of vertices andm is the number of edges in the graph.A preliminary version of this paper was presented at the19th Annual ACM Symposium on Theory of Computing, New York, NY, May 1987.Supported by NSF Grant DCR 8514961.Supported by NSF Grant ECS 8404866 and the Semiconductor Research Corporation Grant 86-12-109.     

A fast algorithm for scalar Nevanlinna-Pick interpolation

Summary In this paper, we derive a fast algorithm for the scalar Nevanlinna-Pick interpolation. Givenn distinct pointsz _i in the unit disk |z|<1 andn complex numbersw _i satisfying the Pick condition for 1in, the new Nevanlinna-Pick interpolation algorithm requires onlyO(n) arithmetic operations to evaluate the interpolatory rational function at a particular value ofz, in contrast to the classical algorithm which requiresO(n ²) arithmetic operations to compute the so-called Fenyves array (which is inherent in the classical algorithm). The new algorithm bypasses the generation of the Fenyves array to speed up the computation, and also yields a parallel scheme requiring onlyO(logn) arithmetic operations on a concurrent-read, exclusive-write parallel random access machine withn processors. We must remark that the rational functionf(z) computed by the new algorithm is one degree higher than the function computed by the classical algorithm.Supported in part by the US Army Research Office Grant No. DAAL03-91-G-0106     

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.     

An improved Monte Carlo factorization algorithm

Pollard's Monte Carlo factorization algorithm usually finds a factor of a composite integerN inO(N ^1/4) arithmetic operations. The algorithm is based on a cycle-finding algorithm of Floyd. We describe a cycle-finding algorithm which is about 36 percent faster than Floyd's (on the average), and apply it to give a Monte Carlo factorization algorithm which is similar to Pollard's but about 24 percent faster.     

On the maximum cardinality search lower bound for treewidth

The Maximum Cardinality Search (MCS) algorithm visits the vertices of a graph in some order, such that at each step, an unvisited vertex that has the largest number of visited neighbours becomes visited. A maximum cardinality search ordering (MCS-ordering) of a graph is an ordering of the vertices that can be generated by the MCS algorithm. The visited degree of a vertex v in an MCS-ordering is the number of neighbours of v that are before v in the ordering. The visited degree of an MCS-ordering ψ of G is the maximum visited degree over all vertices v in ψ. The maximum visited degree over all MCS-orderings of graph G is called its maximum visited degree. Lucena [A new lower bound for tree-width using maximum cardinality search, SIAM J. Discrete Math. 16 (2003) 345-353] showed that the treewidth of a graph G is at least its maximum visited degree.We show that the maximum visited degree is of size O(logn) for planar graphs, and give examples of planar graphs G with maximum visited degree k with O(k!) vertices, for all k∈N. Given a graph G, it is NP-complete to determine if its maximum visited degree is at least k, for any fixed k?7. Also, this problem does not have a polynomial time approximation algorithm with constant ratio, unless P=NP. Variants of the problem are also shown to be NP-complete.In this paper, we also propose some heuristics for the problem, and report on an experimental analysis of them. Several tiebreakers for the MCS algorithm are proposed and evaluated. We also give heuristics that give upper bounds on the value of the maximum visited degree of a graph, which appear to give results close to optimal on many graphs from real life applications.     

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.     

Independence and port oracles for matroids,with an application to computational learning theory

Given a matroidM with distinguished elemente, aport oracie with respect toe reports whether or not a given subset contains a circuit that containse. The first main result of this paper is an algorithm for computing ane-based ear decomposition (that is, an ear decomposition every circuit of which contains elemente) of a matroid using only a polynomial number of elementary operations and port oracle calls. In the case thatM is binary, the incidence vectors of the circuits in the ear decomposition form a matrix representation forM. Thus, this algorithm solves a problem in computational learning theory; it learns the class ofbinary matroid port (BMP) functions with membership queries in polynomial time. In this context, the algorithm generalizes results of Angluin, Hellerstein, and Karpinski [1], and Raghavan and Schach [17], who showed that certain subclasses of the BMP functions are learnable in polynomial time using membership queries. The second main result of this paper is an algorithm for testing independence of a given input set of the matroidM. This algorithm, which uses the ear decomposition algorithm as a subroutine, uses only a polynomial number of elementary operations and port oracle calls. The algorithm proves a constructive version of an early theorem of Lehman [13], which states that the port of a connected matroid uniquely determines the matroid.Research partially funded by NSF PYI Grant No. DDM-91-96083.Research partially funded by NSF Grant No CCR-92-10957.     

On the Complexity of Parallel Algorithms for Computing Inverses in GF(2^m) with m Prime

Inversion over a finite field is usually an expensive operation which is a crucial issue in many applications, such as cryptography and error-control codes. In this paper, three different strategies for computing the inverse over binary finite fields , called Eulerian, Gaussian, and Euclidean, respectively, are discussed and compared in terms of time and space complexity. In particular, some new upper and lower bounds to the respective complexities are evaluated.     

Using a Hybrid Evolutionary Algorithm to Minimize Variance in Response Time for Multimedia Object Requests

This research addresses the scheduling problem of multimedia object requests, which is an important problem in information systems, in particular, for World Wide Web applications. The performance measure considered is the variance of response time which is crucial as end users expect fair treatment to their service requests. This problem is known to be NP-hard. The literature survey indicates that two heuristics have been proposed to solve the problem. In this paper, we present a new heuristic, a hybrid evolutionary heuristic, which is shown to perform much better than the two existing ones, e.g., the overall average errors of the existing ones are 1.012 and 2.042 while the error of the proposed hybrid evolutionary heuristic is 0.154.     

A primal-dual approximation algorithm for generalized steiner network problems

We present the first polynomial-time approximation algorithm for finding a minimum-cost subgraph having at least a specified number of edges in each cut. This class of problems includes, among others, the generalized Steiner network problem, also called the survivable network design problem. Ifk is the maximum cut requirement of the problem, our solution comes within a factor of 2k of optimal. Our algorithm is primal-dual and shows the importance of this technique in designing approximation algorithms.Research supported by an NSF Graduate Fellowship, DARPA contracts N00014-91-J-1698 and N00014-92-J-1799, and AT&T Bell Laboratories.Research supported in part by Air Force contract F49620-92-J-0125 and DARPA contract N00014-92-J-1799.Part of this work was done while the author was visiting AT&T Bell Laboratories and Bellcore.     

On the complexity of diagram testing

In 1987, Neetil and Rödl [4] claimed to have proved that the problem of finding whether a given graphG can be oriented as the diagram of a partial order is NP-complete. A flaw was discovered in their proof by Thostrup [11]. Neetil and Rödl [5] have since corrected the proof, but the new version is rather complex. We give a simpler and more elementary proof, using a completely different approach.     

Relativization makes contradictions harder for Resolution

We provide a number of simplified and improved separations between pairs of Resolution-with-bounded-conjunction refutation systems, Res(d)$\mathrm{Res}(d)$, as well as their tree-like versions, Res^?(d)${\mathrm{Res}}^{?}(d)$. The contradictions we use are natural combinatorial principles: the Least number principle  , _LNPn${\mathrm{LNP}}_n$ and an ordered variant thereof, the Induction principle  , _IPn${\mathrm{IP}}_n$.     

A parallel algorithm for the maximal path problem

In this paper we present anO (log⁵ n) time parallel algorithm for constructing a Maximal Path in an undirected graph. We also give anO (log^1/2+ε) time parallel algorithm for constructing a depth first search tree in an undirected graph. This work was supported in part by an IBM Faculty Development Award, an NSF Graduate Fellowship, and NSF grant DCR-8351757.