Search

We propose new optimal matching techniques for large administrative data sets. In current practice, very large matched samples are constructed by subdividing the population and solving a series of smaller problems, for instance, matching men to men and separately matching women to women. Without simplification of some kind, the time required to optimally match $T$ treated individuals to $T$ controls selected from $C\geq T$ potential controls grows much faster than linearly with the number of people to be matched—the required time is of order $O\{(T+C)^{3}\}$—so splitting one large problem into many small problems greatly accelerates the computations. This common practice has several disadvantages that we describe. In its place, we propose a single match, using everyone, that accelerates the computations in a different way. In particular, we use an iterative form of Glover’s algorithm for a doubly convex bipartite graph to determine an optimal caliper for the propensity score, radically reducing the number of candidate matches; then we optimally match in a large but much sparser graph. In this graph, a modified form of near-fine balance can be used on a much larger scale, improving its effectiveness. We illustrate the method using data from US Medicaid, matching children receiving surgery at a children’s hospital to similar children receiving surgery at a hospital that mostly treats adults. In the example, we form 38,841 matched pairs from 159,527 potential controls, controlling for 29 covariates plus 463 Principal Surgical Procedures, plus 973 Principal Diagnoses. The method is implemented in an $\mathtt{R}$ package $\mathtt{bigmatch}$ available from $\mathtt{CRAN}$.

The problems of counting independent sets, maximal independent sets, and independent perfect dominating sets are #P-complete for bipartite graphs, but can be solved in polynomial time for convex bipartite graphs, which are a subclass of bipartite graphs This paper studies these problems for tree convex bipartite graphs, which are a class of graphs between bipartite graphs and convex bipartite graphs. A bipartite graph G with bipartition (XY) is called tree convex, if a tree T defined on X exists, such that for every vertex y in Y, the neighbors of y form a subtree of T If the associated tree T is simply a path, then G is just a convex bipartite graph. This paper first proves that the problems of counting independent sets, maximal independent sets, and independent perfect dominating sets remain #P-complete for tree convex bipartite graphs even when the associated tree T is only a comb or a star. This paper then presents polynomial-time algorithms to solve these problems for tree convex bipartite graphs when the associated tree T is restricted to a triad, which consists of three paths with one common endpoint.

A left vertex weighted convex bipartite graph (LWCBG) is a bipartite graph $$G=(X,Y,E)$$G=(X,Y,E) in which the neighbors of each $$x\in X$$xźX form an interval in $$Y$$Y where $$Y$$Y is linearly ordered, and each $$x\in X$$xźX has an associated weight. This paper considers the problem of maintaining a maximum weight matching in a dynamic LWCBG. The graph is subject to the updates of vertex and edge insertions and deletions. Our dynamic algorithms maintain the update operations in $$O(\log ^2{|V|})$$O(log2|V|) amortized time per update, obtain the matching status of a vertex (whether it is matched) in constant worst-case time, and find the pair of a matched vertex (with which it is matched) in worst-case $$O(k)$$O(k) time, where $$k$$k is not greater than the cardinality of the maximum weight matching. That achieves the same time bound as the best known solution for the problem of the unweighted version.

We consider computing a maximum non-crossing matching in convex bipartite graphs. For a convex bipartite graph of n vertices and m edges, we present an O ( n log n ) time algorithm for finding a maximum non-crossing matching in the graph. The previous best algorithm takes O ( m + n log n ) time (Malucelli et?al., 1993). Since m = ? ( n 2 ) in the worst case, our result improves the previous work.

For a connected graph, the Hamiltonian cycle (path) is a simple cycle (path) that spans all the vertices in the graph. It is known from \cite{muller,garey} that HAMILTONIAN CYCLE (PATH) are NP-complete in general graphs and chordal bipartite graphs. A convex bipartite graph $G$ with bipartition $(X,Y)$ and an ordering $X=(x_1,\ldots,x_n)$, is a bipartite graph such that for each $y \in Y$, the neighborhood of $y$ in $X$ appears consecutively. $G$ is said to have convexity with respect to $X$. Further, convex bipartite graphs are a subclass of chordal bipartite graphs. In this paper, we present a necessary and sufficient condition for the existence of a Hamiltonian cycle in convex bipartite graphs and further we obtain a linear-time algorithm for this graph class. We also show that Chvatal's necessary condition is sufficient for convex bipartite graphs. The closely related problem is HAMILTONIAN PATH whose complexity is open in convex bipartite graphs. We classify the class of convex bipartite graphs as {\em monotone} and {\em non-monotone} graphs. For monotone convex bipartite graphs, we present a linear-time algorithm to output a Hamiltonian path. We believe that these results can be used to obtain algorithms for Hamiltonian path problem in non-monotone convex bipartite graphs. It is important to highlight (a) in \cite{keil,esha}, it is incorrectly claimed that Hamiltonian path problem in convex bipartite graphs is polynomial-time solvable by referring to \cite{muller} which actually discusses Hamiltonian cycle (b) the algorithm appeared in \cite{esha} for the longest path problem (Hamiltonian path problem) in biconvex and convex bipartite graphs have an error and it does not compute an optimum solution always. We present an infinite set of counterexamples in support of our claim.

Connected domination, i.e. the problem of finding a minimum connected dominating set in a graph, was known to be $$\mathcal {NP}$$ NP -complete for chordal bipartite graphs, but to be tractable for convex bipartite graphs. In this paper, connected domination is shown to be tractable for circular- and triad-convex bipartite graphs respectively, by efficient reductions from these graphs to convex bipartite graphs.

A set D of vertices of a graph G=(V,E) is a dominating set of G if every vertex in [email protected]?D has at least one neighbor in D. A dominating set D of G is a paired-dominating set of G if the induced subgraph, G[D], has a perfect matching. The paired-domination problem is for a given graph G and a positive integer k to answer if G has a paired-dominating set of size at most k. The paired-domination problem is known to be NP-complete even for bipartite graphs. In this paper, we propose a linear time algorithm to compute a minimum paired-dominating set of a convex bipartite graph.

A bipartite graph G=(U,W,E) with vertex set V=U∪W is convex if there exists an ordering of the vertices of W such that for each u∈U, the neighbors of u are consecutive in W. A compact representation of a convex bipartite graph for specifying such an ordering can be computed in O(|V|+|E|) time. The paired-domination problem on bipartite graphs has been shown to be NP-complete. The complexity of the paired-domination problem on convex bipartite graphs has remained unknown. In this paper, we present an O(|V|) time algorithm to solve the paired-domination problem on convex bipartite graphs given a compact representation. As a byproduct, we show that our algorithm can be directly applied to solve the total domination problem on convex bipartite graphs in the same time bound.

Matchings in convex bipartite graphs correspond to the problem of scheduling unit-length tasks on a single disjunctive resource, given a release time and a deadline for every task. The unweighted case was studied by several authors since Glover first considered the problem in 1967 [Glover, F. 1967. Maximum matching in convex bipartite graphs. Naval Res. Logist. Quart. 14 313–316] and until 1996, when Steiner and Yeomans found an algorithm whose running time is linear in the number of tasks [Steiner, G., J. S. Yeomans. 1996. A linear time algorithm for determining maximum matchings in convex, bipartite graphs. Comput. Math. Appl. 31(12) 91–96]. We address a weighted variant of this problem. Given a node-weighted convex bipartite graph G=(X, Y, E) (where Y is linearly ordered and the neighborhood of each node of X is an interval of Y), we show that it is possible to find an X-perfect matching of maximum (or minimum) weight in O(|E| + |Y| log |X|) time and O(|X| + |Y|) space. For the case in which only the nodes of Y are weighted and their weights are positive, the algorithm can be used to find a maximum-weight (not necessarily X-perfect) matching.

We present an efficient parallel algorithm for scheduling n unit length tasks on m identical processors when the precedence graphs are interval orders. Our algorithm requires O(log2 v + (n log n)/v) time and O(nv2 + n2) operations on the CREW PRAM, where v can be any number between 1 and n. By choosing v = √n, we obtain an O(√n log n)-time algorithm with O(n2) operations. For v = n/log n, we have an O(log2 n)-time algorithm with O(n3/log2 n) operations. The previous solution takes O(log2 n) time with O(n3 log2 n) operations on the CREW PRAM. Our improvement is mainly due to a simple dynamic programming recurrence for computing the lengths of optimal schedules and a reduction of the m-processor scheduling problem for interval orders to that of finding a maximum matching in a convex bipartite graph.

This paper considers the problem of maintaining a maximum weight matching in a dynamic vertex weighted convex bipartite graph \({G=(X,Y,E)}\), in which the neighbors of each \({x\in X}\) form an interval of \({Y}\) where Y is linearly ordered, and each vertex has an associated weight. The graph is subject to insertions and deletions of vertices and edges. Our algorithm supports the update operations in \({O(\log ^2{|V|})}\) amortized time, obtains the matching status of a vertex (whether it is matched) in constant worst-case time, and finds the mate of a matched vertex (with which it is matched) in polylogarithmic worst-case time. Our solution is more efficient than the best known solution for the problem in the unweighted version.

An optimal parallel algorithm for computing all-pair shortest paths on doubly convex bipartite graphs is presented here. The input is a (0,1)-matrix with consecutive 1s in each of its rows and columns that represents a doubly convex bipartite graph. Our parallel algorithm runs in O(long n) time with O( n 2 log n) processors on an EREW PRAM and is time-and-work-optimal. As a by-product, we show that the problem can be solved by a sequential algorithm in O(n2) time optimally on any adjacency list or matrix representing a doubly convex bipartite graph. The result in this paper, improves a recent work on the problem for bipartite permutation graphs which are properly contained in doubly convex bipartite graphs.

The k-chain subgraph cover problem asks if the edge set of a given bipartite graph G is the union of the edge sets of k chain graphs, where each chain graph is a subgraph of G. Although the k-chain subgraph cover problem is known to be NP-complete for the class of bipartite graphs, it is still unknown whether this problem is NP-complete or polynomial-time solvable for subclasses of bipartite graphs. In this paper, we answer this question partially by showing that this problem for an important subclass of bipartite graphs, termed convex bipartite graphs, belongs to not only the class P, but also the class NC. More specifically, we show that the k-chain subgraph cover problem on the convex bipartite graph can be solved in O(m2) time sequentially or O(log2n) time in parallel using O(m3) processors on the CRCW PRAM, where n and m denote the number of vertices and edges, respectively.

We consider the problem which is dynamically maintaining a maximum weight matching in a left weighted convex bipartite graph G = (V,E), V = X ∪ Y, in which each x ∈ X has an associated weight, and neighbors of each x ∈ X form an interval in the ordered Y set. The maintenance includes update operations (vertices and edges insertions and deletions) and query operations (inquiries of a vertex matching information). We reduce this problem to the corresponding unweighted problem and design an algorithm that maintains the update operations in O(log3|V|) amortized time per update. In addition, we develop a data structure to obtain the matching status of a vertex (whether it is matched) in constant worst-case time, and find the pair of a matched vertex (with which it is matched) in worst-case O(k) time, where k is not greater than the cardinality of the maximum weight matching.

A bipartite graph G = (V, W, E) is called convex if the vertices in W can be ordered in such a way that the elements of W adjacent to any vertex υ ϵ V form an interval (i.e. a sequence consecutively numbered vertices). Such a graph can be represented in a compact form that requires O(n) space, where n = max{¦V¦, ¦W¦} . Given a convex bipartite graph G in the compact form Dekel and Sahni designed an O(log2(n))-time, n-processor EREW PRAM algorithm to compute a maximum matching in G. We show that the matching produced by their algorithm can be used to construct optimally in parallel a maximum set of independent vertices. Our algorithm runs in O(logn) time with n logn processors on an Arbitrary CRCW PRAM.

The problem of determining the maximum matching in a convex bipartite graph, G = (V1, V2, E), is considered. It is shown that by using the appropriate data structures, the maximum matching problem can be efficiently transformed into an off-line minimum problem. Since the off-line minimum problem has been shown to be linear, the maximum matching in a convex bipartite graph can be determined in O(|V1|) time.

In this paper, we address the problem of finding a maximum matching for a convex bipartite graph on a mesh-connected computer (MCC). We shall show that this can be done in optimal time on MCC by designing the efficient merge and division schemes in bottom-up and top-down approach respectively.

Given n points in a circular region C in the plane, we study the problem of moving these points to the boundary of C to form a regular n-gon such that the maximum of the Euclidean distances traveled by the points is minimized. These problems find applications in mobile sensor barrier coverage of wireless sensor networks. The problem further has two versions: the decision version and optimization version. In this paper, we present an O(nlog2 n) time algorithm for the decision version and an O(nlog3 n) time algorithm for the optimization version. The previously best algorithms for these two problem versions take O(n 3.5) time and O(n 3.5logn) time, respectively. A by-product of our techniques is an algorithm for dynamically maintaining the maximum matching of a circular convex bipartite graph; our algorithm performs each vertex insertion or deletion on the graph in O(log2 n) time. This result may be interesting in its own right.

An independent dominating set in a graph is a subset of vertices, such that every vertex outside this subset has a neighbor in this subset (dominating), and the induced subgraph of this subset contains no edge (independent). It was known that finding the minimum independent dominating set (Independent Domination) is $\cal{NP}$ -complete on bipartite graphs, but tractable on convex bipartite graphs. A bipartite graph is called tree convex, if there is a tree defined on one part of the vertices, such that for every vertex in another part, the neighborhood of this vertex is a connected subtree. A convex bipartite graph is just a tree convex one where the tree is a path. We find that the sum of larger-than-two degrees of the tree is a key quantity to classify the computational complexity of independent domination on tree convex bipartite graphs. That is, when the sum is bounded by a constant, the problem is tractable, but when the sum is unbounded, and even when the maximum degree of the tree is bounded, the problem is $\cal{NP}$ -complete.

We consider computing a maximum non-crossing matching in convex bipartite graphs. For a convex bipartite graph of n vertices and m edges, we present an O (n logn ) time algorithm for finding a maximum non-crossing matching in the graph. The previous best algorithm for this problem takes O (m +n logn ) time. Since m =Θ(n 2) in the worst case, our result improves the previous solution for large m .

Given $n$ points in a circular region $C$ in the plane, we study the problems of moving the $n$ points to its boundary to form a regular $n$-gon such that the maximum (min-max) or the sum (min-sum) of the Euclidean distances traveled by the points is minimized. The problems have applications, e.g., in mobile sensor barrier coverage of wireless sensor networks. The min-max problem further has two versions: the decision version and optimization version. For the min-max problem, we present an $O(n\log^2 n)$ time algorithm for the decision version and an $O(n\log^3 n)$ time algorithm for the optimization version. The previously best algorithms for the two problem versions take $O(n^{3.5})$ time and $O(n^{3.5}\log n)$ time, respectively. For the min-sum problem, we show that a special case with all points initially lying on the boundary of the circular region can be solved in $O(n^2)$ time, improving a previous $O(n^4)$ time solution. For the general min-sum problem, we present a 3-approximation $O(n^2)$ time algorithm, improving the previous $(1+\pi)$-approximation $O(n^2)$ time algorithm. A by-product of our techniques is an algorithm for dynamically maintaining the maximum matching of a circular convex bipartite graph; our algorithm can handle each vertex insertion or deletion on the graph in $O(\log^2 n)$ time. This result is interesting in its own right., Comment: 18 pages, 2 figures

We consider the problem of maintaining a maximum matching in a convex bipartite graph G = (V,E) under a set of update operations which includes insertions and deletions of vertices and edges. It is not hard to show that it is impossible to maintain an explicit representation of a maximum matching in sub-linear time per operation, even in the amortized sense. Despite this difficulty, we develop a data structure which maintains the set of vertices that participate in a maximum matching in O(log2 |V|) amortized time per update and reports the status of a vertex (matched or unmatched) in constant worst-case time. Our structure can report the mate of a matched vertex in the maximum matching in worst-case O(min{k log2 |V |+log |V|, |V| log |V|}) time, where k is the number of update operations since the last query for the same pair of vertices was made. In addition, we give an O(√|V| log2 |V|)-time amortized bound for this pair query.

A first polynomial time algorithm for the computation of the jump number of a convex bipartite graph is presented. The algorithm uses dynamic programming methods.

A bipartite graph G = (V,W,E) is convex if there exists an ordering of the vertices of W such that, for each v /spl isin/ V, the neighbors of v are consecutive in W. We describe a BSP/CGM algorithm for finding a maximum matching in a convex bipartite graph. For p processors, the algorithm runs in time O((|V|/p)lg(|V|/p)lgp) and it uses O(lgp) communication rounds.

Optical communication is attracting more and more attention because of its huge bandwidth to meet the ever increasing demand of emerging computing/networking applications. In this paper we study distributed scheduling algorithms to resolve output contentions in WDM optical interconnects with wavelength conversion ability. We consider the general case of limited range wavelength conversion, including the full range wavelength conversion. Two types of limited range wavelength conversions, circular symmetrical and non circular symmetrical, are studied. We introduce the request graph and show that finding the largest group of contention-free connection requests to achieve maximum network throughput is equivalent to finding a maximum matching in the request graph. Compared with the existing algorithm for finding a maximum matching in an arbitrary bipartite graph with time complexity O(N/sup 3/2/ k /sup 3/2/d), the algorithms we present have time complexity of O(k) and O(dk) (independent of interconnect size N) for non-circular symmetrical and circular symmetrical wavelength conversion, respectively, where k is the number of wavelengths per fiber and d is the conversion degree. In addition, our algorithms can be easily implemented in hardware, and used for time slotted WDM optical interconnects where connections hold for different number of time slots.

This paper describes the design of a linear systolic array algorithm and a VLSI architecture for finding the maximum matching in a convex bipartite graph. The design is based on a systolic architecture that fully utilizes the principles of pipelining and parallelism in order to obtain high speed and throughput. The architecture is scalable and the algorithm is partitionable, i.e., large size problems can be partitioned and executed on a fixed sized array. The PE organization is simple and the architecture does not require any local or global memory. The proposed hardware could be used in various applications such as logic synthesis and channel routing in VLSI CAD, collision avoidance in robotics etc. The proposed chip is estimated to operate at a frequency of 100 MHz based on 1-micron SCMOS technology.

We address the problem of finding a maximum matching for a convex bipartite graph on a mesh-connected computer (MCC). We show that this can be done in optimal time on MCC by designing the efficient merge and division schemes in bottom-up and top-down approach respectively. >

We present an efficient parallel algorithm for scheduling n unit length tasks on m identical processors when the precedence graphs are interval orders. Our algorithm requires O(log2 v + (n log n)=v) time and O(nv2 + n2) operations on the CREW PRAM, where v ≤ n is a parameter. By choosing v = √n, we obtain an O(√n log n)-time algorithm with O(n2) operations. For v = n/log n, we have an O(log2 n)- time algorithm with O(n3/log2 n) operations. The previous solution takes O(log2 n) time with O(n3 log2 n) operations on the CREW PRAM. Our improvement is mainly due to a reduction of the m-processor scheduling problem for interval orders to that of finding a maximum matching in a convex bipartite graph.

Shows that the problem of scheduling n unit-length tasks on two identical processors, for the case where the precedence constraint is an interval order, can be solved in O(log/sup 2//spl nu/+(n log n)//spl nu/) time with O(n/spl nu//sup 2/+n/sup 2/) operations on a CREW PRAM, where /spl nu//spl les/n is a parameter. By choosing /spl nu/=/spl radic/n, we obtain an O(/spl radic/n log n)-time algorithm in O(n/sup 2/) operations. For /spl nu/=n/log n, we have an O(log/sup 2/n)-time algorithm in O(n/sup 3//log/sup 2/n) operations. The best previously-known solution takes O(log/sup 2/n) time with O(n/sup 3/ log/sup 2/n) operations on a CREW PRAM. Our improvement is mainly caused by reducing the two-processor scheduling problem for interval orders to that of finding a maximum matching in a convex bipartite graph, which is a new approach.

A bipartite graph G=(A, B, E) is convex on the vertex set A if A can be ordered so that for each element b in the vertex set B the elements of A connected to b form an interval of A; G is doubly convex if it is convex on both A and B. Letting ¦A¦=m and ¦B¦=n, in this paper we describe maximum matching algorithms which run in time O(m + nA(n)) on convex graphs (where A(n) is a very slowly growing function related to a functional inverse of Ackermann's function), and in time O(m+n) on doubly convex graphs. We also show that, given a maximum matching in a convex bipartite graph G, a corresponding maximum set of independent vertices can be found in time O(m+n). Finally, we briefly discuss some generalizations of convex bipartite graphs and some extensions of the previously discussed techniques to instances in scheduling theory.

A special matching problem arising in industry is shown to be solvable by an algorithm of the form: match objects ai and bj if they satisfy a local optirnality criterion based on a ranking of currently unmatched objects. When no ai and bi remain that can be matched, the largest number of acceptable matches has been found.

We present a coarse grained parallel algorithm for computing a maximum matching in a convex bipartite graph G=(A,B,E). For p processors with N/p memory per processor, N=|A|+|B|,N/p/spl ges/p, the algorithm requires O(log p) communication rounds and O(T/sub sequ/(n/p,m/p)+n/p log p) local computation, where n=|A|,m=|B| and T/sub sequ/(n,m) is the sequential time complexity for the problem. For the BSP model, this implies O(log p) supersteps with O(gN+gn/p log p) communication cost and O(T/sub sequ/(n/p,m/p)+n/p log p) local computation.