A dynamic programming algorithm for tree-like weighted set packing problem

In hierarchical organizations, hierarchical structures naturally correspond to nested sets. That is, we have a collection of sets such that for any two sets, either one of them is a subset of the other, or they are disjoint. In other words, a nested set system forms a hierarchy in the form of a tree structure. The task assignment problem on such hierarchical organizations is a real life problem. In this paper, we introduce the tree-like weighted set packing problem, which is a weighted set packing problem restricted to sets forming tree-like hierarchical structure. We propose a dynamic programming algorithm with cubic time complexity.     

Even faster parameterized cluster deletion and cluster editing

Cluster Deletion and Cluster Editing ask to transform a graph by at most k edge deletions or edge edits, respectively, into a cluster graph, i.e., disjoint union of cliques. Equivalently, a cluster graph has no conflict triples, i.e., two incident edges without a transitive edge. We solve the two problems in time O^?(k^1.415) and O^?(k^1.76), respectively. These results round off our earlier work by considerably improved time bounds. For Cluster Deletion we use a technique that cuts away small connected components that do no longer contribute to the exponential part of the time complexity. As this idea is simple and versatile, it may lead to improvements for several other parameterized graph problems. The improvement for Cluster Editing is achieved by using the full power of an earlier structure theorem for graphs where no edge is in three conflict triples.     

A faster parallel algorithm for a matrix searching problem

We give an improved parallel algorithm for the problem of computing the tube minima of a totally monotonen ×n ×n matrix, an important matrix searching problem that was formalized by Aggarwal and Park and has many applications. Our algorithm runs inO(log logn) time withO(n²/log logn) processors in theCRCW-PRAM model, whereas the previous best ran inO((log logn)²) time withO(n²/(log logn)² processors, also in theCRCW-PRAM model. Thus we improve the speed without any deterioration in thetime ×processors product. Our improved bound immediately translates into improvedCRCW-PRAM bounds for the numerous applications of this problem, including string editing, construction of Huffmann codes and other coding trees, and many other combinatorial and geometric problems.This research was supported by the Office of Naval Research under Grants N00014-84-K-0502 and N00014-86-K-0689, the Air Force Office of Scientific Research under Grant AFOSR-90-0107, the National Science Foundation under Grant DCR-8451393, and the National Library of Medicine under Grant R01-LM05118. Part of the research was done while the author was at Princeton University, visiting the DIMACS center.     

A survey of parameterized algorithms and the complexity of edge modification

The survey is a comprehensive overview of the developing area of parameterized algorithms for graph modification problems. It describes state of the art in kernelization, subexponential algorithms, and parameterized complexity of graph modification. The main focus is on edge modification problems, where the task is to change some adjacencies in a graph to satisfy some required properties. To facilitate further research, we list many open problems in the area.     

A fixed-parameter tractable algorithm for matrix domination

Matrix domination is the NP-complete problem of determining whether a given {0,1} matrix contains a set of k non-zero entries that are in the same row or same column as all other non-zero entries. Using a kernelization and search tree approach, we show the problem to be fixed-parameter tractable with running time .     

Planar packing of trees and spider trees

In [A. García, C. Hernando, F. Hurtado, M. Noy, J. Tejel, Packing trees into planar graphs, J. Graph Theory (2002) 172-181] García et al. conjectured that for every two non-star trees there exists a planar graph containing them as edge-disjoint subgraphs. In this paper we prove the conjecture in the case in which one of the trees is a spider tree.     

A note on maximum independent set and related problems on box graphs

A box graph is the intersection graph of orthogonal rectangles in the plane. We show that maximum independent set and minimum vertex cover on box graphs can be solved in subexponential time, more precisely, in time , by applying Miller's simple cycle planar separator theorem [J. Comput. System Sci. 32 (1986) 265-279] (in spite of the fact that the input box graph might be strongly non-planar).     

An algorithm for partitioning trees augmented with sibling edges

We investigate a special case of the graph partitioning problem: the partitioning of a sibling graph which is an ordered tree augmented with edges connecting consecutive nodes that share a common parent. We describe the algorithm, XS, and present a proof of its correctness.     

Solving a system of difference constraints with variables restricted to a finite set

An algorithm is given for the solution of a system of difference constraints where the variables must take on values from a given finite set of real numbers.     

Approximation algorithms for a hierarchically structured bin packing problem

In this paper we study a variant of the bin packing problem in which the items to be packed are structured as the leaves of a tree. The problem is motivated by document organization and retrieval. We show that the problem is NP-hard and we give approximation algorithms for the general case and for the particular case in which all the items have the same size.     

A note on computing set overlap classes

Let V be a finite set of n elements and F={X₁,X₂,…,Xm} a family of m subsets of V. Two sets Xi and Xj of F overlap if Xi∩Xj≠∅, Xj?Xi≠∅, and Xi?Xj≠∅. Two sets X,Y∈F are in the same overlap class if there is a series X=X₁,X₂,…,Xk=Y of sets of F in which each XiXi+1 overlaps. In this note, we focus on efficiently identifying all overlap classes in time. We thus revisit the clever algorithm of Dahlhaus [E. Dahlhaus, Parallel algorithms for hierarchical clustering and applications to split decomposition and parity graph recognition, J. Algorithms 36 (2) (2000) 205-240] of which we give a clear presentation and that we simplify to make it practical and implementable in its real worst case complexity. An useful variant of Dahlhaus's approach is also explained.     

Simplified tight analysis of Johnson's algorithm

In their paper “Tight bound on Johnson's algorithm for maximum satisfiability” [J. Comput. System Sci. 58 (3) (1999) 622-640] Chen, Friesen and Zheng provided a tight bound on the approximation ratio of Johnson's algorithm for Maximum Satisfiability [J. Comput. System Sci. 9 (3) (1974) 256-278]. We give a simplified proof of their result and investigate to what extent it may be generalized to non-Boolean domains.     

A variant of the Ford-Johnson algorithm that is more space efficient

A variant of the Ford-Johnson or merge insertion sorting algorithm that we called four Ford-Johnson (₄FJ, for short) is presented and proved to execute exactly the same number of comparisons than the Ford-Johnson algorithm. The main advantage of our algorithm is that, instead of recursively working over lists of size the half of the input, as the Ford-Johnson algorithm does, ₄FJ recursively works over lists of size the quarter of the input. This allows for implementations of data structures for coordinating the recursive calls of size only 33% of the ones needed for the Ford-Johnson algorithm.     

Comments on the hierarchically structured bin packing problem

We study the hierarchically structured bin packing problem. In this problem, the items to be packed into bins are at the leaves of a tree. The objective of the packing is to minimize the total number of bins into which the descendants of an internal node are packed, summed over all internal nodes. We investigate an existing algorithm and make a correction to the analysis of its approximation ratio. Further results regarding the structure of an optimal solution and a strengthened inapproximability result are given.     

A Relax-and-Cut algorithm for the set partitioning problem

Relax-and-Cut algorithms offer an alternative to strengthen Lagrangian relaxation bounds. The main idea behind these algorithms is to dynamically select and dualize inequalities (cuts) within a Lagrangian relaxation framework. This paper proposes a Relax-and-Cut algorithm for the Set Partitioning Problem. Computational tests are reported for benchmark instances from the literature. For Set Partitioning instances with integrality gaps, a variant of the classical Lagrangian relaxation is often used in the literature. It introduces a knapsack constraint to the standard formulation of the problem. Our results indicate that the proposed Relax-and-Cut algorithm outperforms the latter approach in terms of lower bound quality. Furthermore, it turns out to be very competitive in terms of CPU time. Decisive in achieving that performance was the implementation of dominance rules to manage inequalities in the cut pool. The Relax-and-Cut framework proposed here could also be used as a preprocessing tool for Linear Integer Programming solvers. Computational experiments demonstrated that the combined use of our framework and XPRESS improved the performance of that Linear Integer Programming solver for the test sets used in this study.     

Improved FPT algorithm for feedback vertex set problem in bipartite tournament

We present an O(k³n²+n³) time FPT algorithm for the feedback vertex set problem in a bipartite tournament on n vertices with integral weights. This improves the previously best known O(k^3.12n⁴) time FPT algorithm for the problem.     

Efficient parameterized string matching

In parameterized string matching the pattern P matches a substring t of the text T if there exist a bijective mapping from the symbols of P to the symbols of t. We give simple and practical algorithms for finding all such pattern occurrences in sublinear time on average. The algorithms work for a single and multiple patterns.     

On the All-Farthest-Segments problem for a planar set of points

In this note, we outline a very simple algorithm for the following problem: Given a set S of n points p₁,p₂,p₃,…,pn in the plane, we have O(n²) segments implicitly defined on pairs of these n points. For each point pi, find a segment from this set of implicitly defined segments that is farthest from pi. The time complexity of our algorithm is in O(nh+nlogn), where n is the number of input points, and h is the number of vertices on the convex hull of S.