Let @math and @math be sets of @math red and @math blue points in the plane, respectively, with @math . Let @math be a perfect matching between points from @math and @math , using @math straight line segments to match the points, that is, each point is an endpoint of exactly one line segment, and each line segment has one red and one blue endpoint. We forbid line segments to cross. Denote the length of a longest line segment in @math with @math , which we also call the [ ] value, bn of @math . We aim to find a matching under given constraints that minimizes @math . Any such matching is called a [ ] bottleneck matching of @math .
A variant of the bichromatic case is the so-called bicolored (or multicolored, when there are arbitrary many colors) case, where only the points of the same color are allowed to be matched. Abu-Affash, Bhore and Carmi in @cite_12 examined bicolored matchings that minimize the number of crossings between edges matching different color sets. They presented an algorithm to compute a bottleneck matching of points in convex position among all matchings that have no crossings of this kind.
@cite_12
2289848075 1001549597 2167652126 2171323859 1898334569 2963714020 2006040238 2046633098 2797253418 2772780650 2170326985 2045611333 2019186869 2015596743 1970202342 2157562188 2166185329 2119761906 1970818149 1968325900
Motivated by a crane assignment problem, we consider a Euclidean bipartite matching problem with edge-crossing constraints. Specifically, given n red points and n blue points in the plane, we want to construct a perfect matching between red and blue points that minimizes the length of the longest edge, while imposing a constraint that no two edges may cross each other. We show that the problem cannot be approximately solved within a factor less than 1:277 in polynomial time unless P = NP. We give simple dynamic programming algorithms that solve our problem in two special cases, namely (1) the case where the red and blue points form the vertices of a convex polygon and (2) the case where the red points are collinear and the blue points lie to one side of the line through the red points. Let (X ) be a set of multicolored points in the plane such that no three points are collinear and each color appears on at most ( |X| 2 ) points. We show the existence of a non-crossing properly colored geometric perfect matching on (X ) (if (|X| ) is even), and the existence of a non-crossing properly colored geometric spanning tree with maximum degree at most (3 ) on (X ). Moreover, we show the existence of a non-crossing properly colored geometric perfect matching in the plane lattice. In order to prove these our results, we propose an useful lemma that gives a good partition of a sequence of multicolored points. This paper presents an approach to object discovery in a given unlabeled image set, based on mining repetitive spatial configurations of image contours. Contours that similarly deform from one image to another are viewed as collaborating, or, otherwise, conflicting. This is captured by a graph over all pairs of matching contours, whose maximum a posteriori multicoloring assignment is taken to represent the shapes of discovered objects. Multicoloring is conducted by our new Coordinate Ascent Swendsen-Wang cut (CASW). CASW uses the Metropolis-Hastings (MH) reversible jumps to probabilistically sample graph edges, and color nodes. CASW extends SW cut by introducing a regularization in the posterior of multicoloring assignments that prevents the MH jumps to arrive at trivial solutions. Also, CASW seeks to learn parameters of the posterior via maximizing a lower bound of the MH acceptance rate. This speeds up multicoloring iterations, and facilitates MH jumps from local minima. On benchmark datasets, we outperform all existing approaches to unsupervised object discovery. This paper presents a framework of layered graph matching for integrating graph partition and matching. The objective is to find an unknown number of corresponding graph structures in two images. We extract discriminative local primitives from both images and construct a candidacy graph whose vertices are matching candidates (i.e., a pair of primitives) and whose edges are either negative for mutual exclusion or positive for mutual consistence. Then we pose layered graph matching as a multicoloring problem on the candidacy graph and solve it using a composite cluster sampling algorithm. This algorithm assigns some vertices into a number of colors, each being a matched layer, and turns off all the remaining candidates. The algorithm iterates two steps: 1) Sampling the positive and negative edges probabilistically to form a composite cluster, which consists of a few mutually conflicting connected components (CCPs) in different colors and 2) assigning new colors to these CCPs with consistence and exclusion relations maintained, and the assignments are accepted by the Markov Chain Monte Carlo (MCMC) mechanism to preserve detailed balance. This framework demonstrates state-of-the-art performance on several applications, such as multi-object matching with large motion, shape matching and retrieval, and object localization in cluttered background. It is NP-Hard to find a proper 2-coloring of a given 2-colorable (bipartite) hypergraph H. We consider algorithms that will color such a hypergraph using few colors in polynomial time. The results of the paper can be summarized as follows: Let n denote the number of vertices of H and m the number of edges, (i) For bipartite hypergraphs of dimension k there is a polynomial time algorithm which produces a proper coloring using min ( O(n^ 1 - 1 k ),O((m n)^ 1 k - 1 ) )colors, (ii) For 3-uniform bipartite hypergraphs, the bound is reduced to O(n2 9). (iii) For a class of dense 3-uniform bipartite hypergraphs, we have a randomized algorithm which can color optimally. (iv) For a model of random bipartite hypergraphs with edge probability p≥ dn−2, d > O a sufficiently large constant, we can almost surely find a proper 2-coloring. The (∆+1)-coloring problem is a fundamental symmetry breaking problem in distributed computing. We give a new randomized coloring algorithm for (∆+1)-coloring running in O(√log ∆)+ 2^O(√log log n) rounds with probability 1-1 n^Ω(1) in a graph with n nodes and maximum degree ∆. This implies that the (∆+1)-coloring problem is easier than the maximal independent set problem and the maximal matching problem, due to their lower bounds by Kuhn, Moscibroda, and Wattenhofer [PODC'04]. Our algorithm also extends to the list-coloring problem where the palette of each node contains ∆+1 colors. We give simple, deterministic, distributed algorithms for computing maximal matchings, maximal independent sets and colourings. We show that edge colourings with at most 2Δ-1 colours, and maximal matchings can be computed within O(log* n + Δ) deterministic rounds, where Δ is the maximum degree of the network. We also show how to find maximal independent sets and (Δ + 1)-vertex colourings within O(log* n + Δ2) deterministic rounds. All hidden constants are very small and the algorithms are very simple. We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has to be conflict-free, in the sense that in every interval I there is a color that appears exactly once in I. We present several deterministic and randomized algorithms for achieving this goal, and analyze their performance, that is, the maximum number of colors that they need to use, as a function of the number n of inserted points. We first show that a natural and simple (deterministic) approach may perform rather poorly, requiring Ω(√n) colors in the worst case. We then modify this approach, to obtain an efficient deterministic algorithm that uses a maximum of Θ(log2 n) colors. Next, we present two randomized solutions. The first algorithm requires an expected number of at most O(log2 n) colors, and produces a coloring which is valid with high probability, and the second one, which is a variant of our efficient deterministic algorithm, requires an expected number of at most O(log n log log n) colors but always produces a valid coloring. We also analyze the performance of the simplest proposed algorithm when the points are inserted in a random order, and present an incomplete analysis that indicates that, with high probability, it uses only O(log n) colors. Finally, we show that in the extension of this problem to two dimensions, where the relevant ranges are disks, n colors may be required in the worst case. The average-case behavior for disks, and cases involving other planar ranges, are still open. We give a new randomized distributed algorithm for (Δ +1)-coloring in the LOCAL model, running in O(s log Δ)+ 2O(slog log n) rounds in a graph of maximum degree Δ. This implies that the (Δ +1)-coloring problem is easier than the maximal independent set problem and the maximal matching problem, due to their lower bounds of Ω(min(sflog n log log n, flog Δ log log Δ)) by Kuhn, Moscibroda, and Wattenhofer [PODC’04]. Our algorithm also extends to list-coloring where the palette of each node contains Δ +1 colors. We extend the set of distributed symmetry-breaking techniques by performing a decomposition of graphs into dense and sparse parts. Vertex coloring is one of the classic symmetry breaking problems studied in distributed computing. In this paper we present a new algorithm for (Δ+1)-list coloring in the randomized LOCAL model running in O(log∗n + Detd(poly logn)) time, where Detd(n′) is the deterministic complexity of (deg+1)-list coloring (v’s palette has size deg(v)+1) on n′-vertex graphs. This improves upon a previous randomized algorithm of Harris, Schneider, and Su (STOC 2016). with complexity O(√logΔ + loglogn + Detd(poly logn)), and (when Δ is sufficiently large) is much faster than the best known deterministic algorithm of Fraigniaud, Heinrich, and Kosowski (FOCS 2016), with complexity O(√Δlog2.5Δ + log* n). Our algorithm appears to be optimal. It matches the Ω(log∗n) randomized lower bound, due to Naor (SIDMA 1991) and sort of matches the Ω(Det(poly logn)) randomized lower bound due to Chang, Kopelowitz, and Pettie (FOCS 2016), where Det is the deterministic complexity of (Δ+1)-list coloring. The best known upper bounds on Detd(n′) and Det(n′) are both 2O(√logn′) by Panconesi and Srinivasan (Journal of Algorithms 1996), and it is quite plausible that the complexities of both problems are the same, asymptotically. In our fractional stereo matching problem, a foreground object with a fractional boundary is blended with a background scene using unknown transparencies. Due to the spatially varying disparities in different layers, one foreground pixel may be blended with different background pixels in stereo images, making the color constancy commonly assumed in traditional stereo matching not hold any more. To tackle this problem, in this paper, we introduce a probabilistic framework constraining the matching of pixel colors, disparities, and alpha values in different layers, and propose an automatic optimization method to solve a maximizing a posterior (MAP) problem using expectation-maximization (EM), given only a short-baseline stereo input image pair. Our method encodes the effect of background occlusion by layer blending without requiring a special detection process. The alpha computation process in our unified framework can be regarded as a new approach by natural image matting, which handles appropriately the situation when the background color is similar to that of the foreground object. We demonstrate the efficacy of our method by experimenting with challenging stereo images and making comparisons with state-of-the-art methods. Bounds are given on the number of colors required to color the edges of a graph (multigraph) such that each color appears at each vertex v at most m(ν) times. The known results and proofs generalize in natural ways. Certain new edge-coloring problems, which have no counterparts when m(ν) = 1 for all ν ϵ V, are studied. We study the entropy landscape of solutions for the bicoloring problem in random graphs, a representative difficult constraint satisfaction problem. Our goal is to classify which types of clusters of solutions are addressed by different algorithms. In the first part of the study we use the cavity method to obtain the number of clusters with a given internal entropy and determine the phase diagram of the problem--e.g., dynamical, rigidity, and satisfiability-unsatisfiability (SAT-UNSAT) transitions. In the second part of the paper we analyze different algorithms and locate their behavior in the entropy landscape of the problem. For instance, we show that a smoothed version of a decimation strategy based on belief propagation is able to find solutions belonging to subdominant clusters even beyond the so-called rigidity transition where the thermodynamically relevant clusters become frozen. These nonequilibrium solutions belong to the most probable unfrozen clusters. In the online F-avoidance edge-coloring game with r colors, a graph on n vertices is generated by randomly adding a new edge at each stage. The player must color each new edge as it appears; the goal is to avoid a monochromatic copy of F. Let N"0(F,r,n) be the threshold function for the number of edges that the player is asymptotically almost surely able to paint before he she loses. Even when F=K"3, the order of magnitude of N"0(F,r,n) is unknown for r>=3. In particular, the only known upper bound is the threshold function for the number of edges in the offline version of the problem, in which an entire random graph on n vertices with m edges is presented to the player to be r edge-colored. We improve the upper bound for the online triangle-avoidance game with r colors, providing the first result that separates the online threshold function from the offline bound for r>=3. This supports a conjecture of Marciniszyn, Spohel, and Steger that the known lower bound is tight for cliques and cycles for all r. Consider a bipartite graph G = (O, D, E) where O and D are origin and destination node sets respectively (O = D = n), and E is a set of edges (i, j), i ∈ O and j ∈ D(E= m). Suppose we draw the origin nodes and the destination nodes arranged in two columns and the edges as straight line segments between origins and destinations. A noncrossing matching is a subset of edges M ⊑ E such that no two edges of M intersect (including intersections at nodes). The Maximum Non Crossing Matching (MNCM) is the problem of finding the noncrossing matching of maximum cardinality. Let p denote the cardinality of the MNCM. Problems arising in several fields can be modelled as MNCM: for example the 3-Side Switch Box in VLSI design has been presented in [2] where an O(n 2) time algorithm is proposed. The problem can be reduced to the one of finding the longest increasing subsequence in a permutation of size m [1]. An algorithm for this problem has been proposed by Fredman and slightly improved by Widmayer and Wong[7]; in our case the algorithm complexity is O(m + (m - p) log (p). In this paper some labeling algorithms for the MNCM, which work directly on the bipartite graph, will be proposed. The overall complexity is improved to O(m log log n) or to O(m + minnp, (m - p) log p). Finally the weighted case is considered. We study deterministic, distributed algorithms for two weak variants of the standard graph coloring problem. We consider defective colorings, i.e., colorings where nodes of a color class may induce a graph of maximum degree d for some parameter d>0. We also look at colorings where a minimum number of multi-chromatic edges is required. For an integer k>0, we call a coloring k-partially proper if every node v has at least min k,deg(v) neighbors with a different color. We show that for all d∈ 1,...,Δ , it is possible to compute a O(Δ2 d2)-coloring with defect d in time O(log*n) where Δ is the largest degree of the network graph. Similarly, for all k∈ 1,...,Δ , a k-partially proper O(k2)-coloring can be computed in O(log*n) rounds. As an application of our weak defective coloring algorithm, we obtain a faster deterministic algorithm for the standard vertex coloring problem on graphs with moderate degrees. We show that in time O(Δ+log*n), a (Δ+1)-coloring can be computed, a task for which the best previous algorithm required time O(Δ*log(Δ) + log*n). The same result holds for the problem of computing a maximal independent set. The dichromatic reflectance model introduced by S. Shafer (1985) predicts that the colour signals of most materials fall on a plane spanned by a vector due to the material and a vector that represents the scene illuminant. Since the illuminant is in the span of all dichromatic planes, colour constancy can be achieved by finding the intersection of two or more planes. Unfortunately, this approach has proven to be hard to get to work in practice. First, segmentation needs to be carried out and second, the actual intersection computation is quite unstable: small changes in the orientation of a dichromatic plane can significantly alter the location of the intersection point. We propose to ameliorate the instability problem by regularising the intersection. Specifically, we introduce a constraint on the colour of the illuminant. We show how the intersection problem in the context of convex and non-convex illuminant constraints, based on the distribution of common light sources, can be solved. This algorithm coupled with the simplest of segmentations results in good estimation results for a large set of real images. Estimation performance is significantly better than for the unconstrained algorithm. We introduce Multi-Trials, a new technique for symmetry breaking for distributed algorithms and apply it to various problems in general graphs. For instance, we present three randomized algorithms for distributed (vertex or edge) coloring improving on previous algorithms and showing a time color trade-off. To get a Δ+1 coloring takes time O(log Δ+ √ log n). To obtain an O(Δ+log1+1 log*nn) coloring takes time O(log* n). This is more than an exponential improvement in time for graphs of polylogarithmic degree. Our fastest algorithm works in constant time using O(Δlog(c) n+ log1+1 c n) colors, where c denotes an arbitrary constant and log(c ) n denotes the c times (recursively) applied logarithm ton. We also use the Multi-Trials technique to compute network decompositions and to compute maximal independent set (MIS), obtaining new results for several graph classes. A 2-coloring of a hypergraph is a mapping from its vertex set to a set of two colors such that no edge is monochromatic. Let H = H(k, n, p) be a random k-uniform hypergraph on a vertex set V of cardinality n, where each k-subset of V is an edge of H with probability p, independently of all other k-subsets. Let m = p(????) denote the expected number of edges in H. Let us say that a sequence of events En holds with high probability (w.h.p.) if limn → ∞ Pr[En] = 1. It is easy to show that if m = c2kn then w.h.p H is not 2-colorable for c > ln 2 2. We prove that there exists a constant c > 0 such that if m = (c2k k)n, then w.h.p H is 2-colorable. 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.