A greedy algorithm for finding a large 2‐matching on a random cubic graph

A 2‐matching of a graph G is a spanning subgraph with maximum degree two. The size of a 2‐matching U is the number of edges in U and this is at least where n is the number of vertices of G and κ denotes the number of components. In this article, we analyze the performance of a greedy algorithm 2greedy for finding a large 2‐matching on a random 3‐regular graph. We prove that with high probability, the algorithm outputs a 2‐matching U with .     

The Stochastic Location-Assignment Problem on a Tree

In the assignment problem units of supply are assigned on a one-to-one basis to units of demand so as to minimize the sum of the cost associated with each supply-to-demand matched pair. Defined on a network, the supplies and demands are located at vertices and the cost of a supply-to-demand matched pair is the distance between them. This paper considers a two-stage stochastic program for locating the units of supply based upon only a probabilistic characterization of demand. The objective of the first-stage location problem is to minimize the expected cost of the second-stage assignment problem. Principal results include showing that the problem is NP-hard on a general network, has a simple solution procedure on a line network, and is solvable by a low order polynomial greedy procedure on a tree network. Potential applications are discussed.     

Optimal Pair Matching With Two Control Groups

In an effort to detect hidden biases due to failure to control for an unobserved covariate, some observational or nonrandomized studies include two control groups selected to systematically vary the unobserved covariate. Comparisons of the treated group and two control groups must, of course, control for imbalances in observed covariates. Using the three groups, we form pairs optimally matched for observed covariates—that is, we optimally construct from observational data an incomplete block design. The incomplete block design may use all available data, or it may use data selectively to produce a balanced incomplete block design, or it may be the basis for constructing a matched sample when expensive outcome information is to be collected only for sampled individuals. The problem of optimal pair matching with two control groups is shown by a series of transformations to be equivalent to a particular form of optimal nonbipartite matching, a problem for which polynomial time algorithms exist. In our examples, we implement the procedure using a nonbipartite matching algorithm due to Derigs. We illustrate the method with data from an observational study of the employment effects of the minimum wage.     

A Note on Optimal Matching With Variable Controls Using the Assignment Algorithm

The assignment algorithm is an old, well-known, widely implemented, fast, combinatorial algorithm for optimal matching in a bipartite graph. This note proposes a method for using the assignment algorithm to solve the problem of optimal matching with a variable number of controls, in which there is a choice not only of who to select as a control for each treated subject, but also of how many controls to have for each treated subject. The strategy uses multiple copies of treated subjects and sinks with zero cost to absorb extra controls. Also, it is shown that an optimal matching with variable numbers of controls cannot be obtained by starting with an optimal pair matching and adding the closest additional controls. An example involving mortality after surgery in Pennsylvania hospitals is used to illustrate the method.     

The ζ(2) limit in the random assignment problem

The random assignment (or bipartite matching) problem asks about A_n=min_π ∑c(i, π(i)), where (c(i, j)) is a n×n matrix with i.i.d. entries, say with exponential(1) distribution, and the minimum is over permutations π. Mézard and Parisi (1987) used the replica method from statistical physics to argue nonrigorously that EA_n→ζ(2)=π²/6. Aldous (1992) identified the limit in terms of a matching problem on a limit infinite tree. Here we construct the optimal matching on the infinite tree. This yields a rigorous proof of the ζ(2) limit and of the conjectured limit distribution of edge‐costs and their rank‐orders in the optimal matching. It also yields the asymptotic essential uniqueness property: every almost‐optimal matching coincides with the optimal matching except on a small proportion of edges. ©2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 381–418, 2001     

Average-optimal string matching

The exact string matching problem is to find the occurrences of a pattern of length m from a text of length n symbols. We develop a novel and unorthodox filtering technique for this problem. Our method is based on transforming the problem into multiple matching of carefully chosen pattern subsequences. While this is seemingly more difficult than the original problem, we show that the idea leads to very simple algorithms that are optimal on average. We then show how our basic method can be used to solve multiple string matching as well as several approximate matching problems in average optimal time. The general method can be applied to many existing string matching algorithms. Our experimental results show that the algorithms perform very well in practice.     

Stable Marriage and Genetic Algorithms: A Fertile Union

We describe a pair of genetic algorithms for solving two stable matching problems. Both stable matching problems we will consider involve a set of applicants for positions and a set of employers. Each applicant and each employer prepares a rank order list of a subset of the actors in the other set. The goal is to find an assignment of applicants to employers in which if applicant a is not assigned to employer b then either a prefers his assignment to b or b prefers its assignment toa . In other words, no applicant/employer pair can both improve their situations by dropping their current assignments in favor of each other. Our goal will be to enumerate the stable matchings. One of the problems we will consider is the well-known stable marriage problem, in which neither applicant nor employer preference lists are linked. In the other problem, we will allow pairs of applicants who form a couple to submit joint rank order lists of ordered pairs of employers.     

Extremal graphs having no matching cuts

A graph G = (V, E) is matching immune if there is no matching cut in G. We show that for any matching immune graph G, |E|≥?3(|V|?1)/2?. This bound is tight, as we define operations that construct, from a given vertex, exactly the class of matching immune graphs that attain the bound. © 2011 Wiley Periodicals, Inc. J Graph Theory 69:206‐222, 2012 .     

Induced matching extendable graphs

We say that a simple graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. The main results of this paper are as follows: (1) For every connected IM-extendable graph G with |V(G)| ≥ 4, the girth g(G) ≤ 4. (2) If G is a connected IM-extendable graph, then |E(G)| ≥ ${3\over 2}|V(G)| - 2$; the equality holds if and only if G ≅ T × K₂, where T is a tree. (3) The only 3-regular connected IM-extendable graphs are C_n × K₂, for n ≥ 3, and C_2n(1, n), for n ≥ 2, where C_2n(1, n) is the graph with 2n vertices x₀, x₁, …, x_2n−1, such that x_ix_j is an edge of C_2n(1, n) if either |i − j| ≡ 1 (mod 2n) or |i − j| ≡ n (mod 2n). © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 203–213, 1998     

PARTITION A GRAPH WITH SMALL DIAMETER INTO TWO INDUCED MATCHINGS

§1　IntroductionGraphs considered in this paper are finite and simple.For a graph G,its vertex setandedge set are denoted by V(G) and E(G) ,respectively.If vertices u and v are connected inG,the distance between u and v,denoted by d G(u,v) ,is the length ofa shortest(u,v) -pathin G.The diameter of a connected graph G is the maximum distance between two verticesof G.For X V(G) ,the neighbor set NG(X) of X is defined byNG(X) ={ y∈V(G) \X:there is x∈X such thatxy∈E(G) } .NG({ x} )…     

An optimal greedy routing algorithm for triangulated polygons

In this paper, we prove that a triangulated polygon G admits a greedy embedding into an appropriate semi-metric space such that using an appropriate distance definition, for any two vertices u and w in G, a most virtual distance decreasing path is always a minimum-edge path between u and w. Therefore, our greedy routing algorithm is optimal. The greedy embedding of G can be obtained in linear time. To the best of our knowledge, this is the first optimal greedy routing algorithm for a nontrivial subcategory of graphs.     

A graphical investigation of error bounds for moment-based queueing approximations

Many approximations of queueing performance measures are based on moment matching. Empirical and theoretical results show that although approximations based on two moments are often accurate, two-moment approximations can be arbitrarily bad and sometimes three-moment approximations are far better. In this paper, we investigate graphically error bounds for two- and three-moment approximations of three performance measures forGI/M/ · type models. Our graphical analysis provides insight into the adequacy of two- and three-moment approximations as a function of standardized moments of the interarrival-time distribution. We also discuss how the behavior of these approximations varies with other model parameters and with the performance measure being approximated.     

Graphs in which some and every maximum matching is uniquely restricted

A matching M in a graph G is uniquely restricted if there is no matching in G that is distinct from M but covers the same vertices as M. Solving a problem posed by Golumbic, Hirst, and Lewenstein, we characterize the graphs in which some maximum matching is uniquely restricted. Solving a problem posed by Levit and Mandrescu, we characterize the graphs in which every maximum matching is uniquely restricted. Both our characterizations lead to efficient recognition algorithms for the corresponding graphs.     

Induced Matching Extendable Graph Powers

A graph G is called induced matching extendable (shortly, IM-extendable) if every induced matching of G is included in a perfect matching of G. A graph G is called strongly IM-extendable if every spanning supergraph of G is IM-extendable. The k-th power of a graph G, denoted by G^k, is the graph with vertex set V(G) in which two vertices are adjacent if and only if the distance between them in G is at most k. We obtain the following two results which give positive answers to two conjectures of Yuan. Result 1. If a connected graph G with |V(G)| even is locally connected, then G² is strongly IM-extendable. Result 2. If G is a 2-connected graph with |V(G)| even, then G³ is strongly IM-extendable. Research Supported by NSFC Fund 10371102.     

Minimizing the total completion time on-line on a single machine, using restarts

We give an algorithm to minimize the total completion time on-line on a single machine, using restarts, with a competitive ratio of 3/2. The optimal competitive ratio without using restarts is 2 for deterministic algorithms and e/(e−1)≈1.582 for randomized algorithms. This is the first restarting algorithm to minimize the total completion time that is proved to be better than an algorithm that does not restart.     

Penny-packings with minimal second moments

We consider the problem of packingn disks of unit diameter in the plane so as to minimize the second moment about their centroid. Our main result is an algorithm which constructs packings that are optimal among hexagonal packings. Using the algorithm, we prove that, except forn=212, then-point packings obtained by Graham and Sloane [1] are optimal among hexagonal packings. We also prove a result that makes precise the intuition that the greedy algorithm of Graham and Sloane produces approximately circular packings.     

Imposing Minimax and Quantile Constraints on Optimal Matching in Observational Studies

Modern methods construct a matched sample by minimizing the total cost of a flow in a network, finding a pairing of treated and control individuals that minimizes the sum of within-pair covariate distances subject to constraints that ensure distributions of covariates are balanced. In aggregate, these methods work well; however, they can exhibit a lack of interest in a small number of pairs with large covariate distances. Here, a new method is proposed for imposing a minimax constraint on a minimum total distance matching. Such a match minimizes the total within-pair distance subject to various constraints including the constraint that the maximum pair difference is as small as possible. In an example with 1391 matched pairs, this constraint eliminates dozens of pairs with moderately large differences in age, but otherwise exhibits the same excellent covariate balance found without this additional constraint. A minimax constraint eliminates edges in the network, and can improve the worst-case time bound for the performance of the minimum cost flow algorithm, that is, a better match from a practical perspective may take less time to construct. The technique adapts ideas for a different problem, the bottleneck assignment problem, whose sole objective is to minimize the maximum within-pair difference; however, here, that objective becomes a constraint on the minimum cost flow problem. The method generalizes. Rather than constrain the maximum distance, it can constrain an order statistic. Alternatively, the method can minimize the maximum difference in propensity scores, and subject to doing that, minimize the maximum robust Mahalanobis distance. An example from labor economics is used to illustrate. Supplementary materials for this article are available online.     

Efficient generation of super condensed neighborhoods

Indexing methods for the approximate string matching problem spend a considerable effort generating condensed neighborhoods. Condensed neighborhoods, however, are not a minimal representation of a pattern neighborhood. Super condensed neighborhoods, proposed in this work, are smaller, provably minimal and can be used to locate approximate matches that can later be extended by on-line search. We present an algorithm for generating Super Condensed Neighborhoods. The algorithm can be implemented either by using dynamic programming or non-deterministic automata. The time complexity is O(ms) for the first case and O(kms) for the second, where m is the pattern size, s is the size of the super condensed neighborhood and k the number of errors. Previous algorithms depended on the size of the condensed neighborhood instead. These algorithms can be implemented using Bit-Parallelism and Increased Bit-Parallelism techniques. Our experimental results show that the resulting algorithms are fast and achieve significant speedups, when compared with the existing proposals that use condensed neighborhoods.     

Greedy linear extensions for minimizing bumps

Let P be a finite poset and let L={x ₁<...n} be a linear extension of P. A bump in L is an ordered pair (x _i , x _i+1) where x _ii+1 in P. The bump number of P is the least integer b(P), such that there exists a linear extension of P with b(P) bumps. We call L optimal if the number of bumps of L is b(P). We call L greedy if x _{i j} for every j>i, whenever (x _i, x _i+1) is a bump. A poset P is called greedy if every greedy linear extension of P is optimal. Our main result is that in a greedy poset every optimal linear extension is greedy. As a consequence, we prove that every greedy poset of bump number k is the linear sum of k+1 greedy posets, each of bump number zero.This research (Math/1406/31) was supported by the Research Center, College of Science, King Saud University, Riyadh, Saudi Arabia.