43243
Rank-maximal matchings
Suppose that each member of a set A of applicants ranks a subset of a set P of posts in an order of preference, possibly involving ties. A matching is a set of (applicant, post) pairs such that each applicant and each post appears in at most one pair. A rank-maximal matching is one in which the maximum possible number of applicants are matched to their first choice post, and subject to that condition, the maximum possible number are matched to their second choice post, and so on. This is a relevant concept in any practical matching situation and it was first studied by Irving [2003].We give an algorithm to compute a rank-maximal matching with running time O(min(n + C,C &sqrt;n)m), where C is the maximal rank of an edge used in a rank-maximal matching, n is the number of applicants and posts and m is the total size of the preference lists.
5720611
A Correctness Certificate for the Stoer-Wagner Min-Cut Algorithm
The Stoer‐Wagner algorithm computes a minimum cut in a weighted undirected graph. The algorithm works inn 1 phases, wheren is the number of nodes ofG. Each phase takes time O.mCn logn/ ,w herem is the number of edges ofG, and computes a pair of vertices s and t and a minimum cut separatings and t . We show how to extend the algorithm such that each phase also computes a maximum flow from s tot . The flow is computed in O.m/ additional time and certifies the cut computed in the phase. © 1999 Elsevier Science B.V. All rights reserved. We give a correctness certificate for the min-cut algorithm of Stoer and Wagner [6]. This algorithm refines the algorithm of Nagamochi and Ibaraki [5,4]; it has the same time complexity, but is simpler. The algorithm is deterministic. There are faster randomized algorithms [2,3]. No certificates are known for the randomized algorithms. Let G be an undirected graph with n vertices and m edges. The algorithm of Stoer and Wagner works inn 1 phases. In each phase it identifies two vertices and a minimum cut separating them and then collapses the two vertices into one. The global min-cut is the minimum cut found in any phase. Each phase runs in time O.mCn logn/. We extend the algorithm such that it also finds a flow equal to the min-cut in each phase. The additional time required to find the flow is O.m/ in each phase.
47385179
Matching Algorithms Are Fast in Sparse Random Graphs
We present an improved average case analysis of the maximum cardinality matching problem. We show that in a bipartite or general random graph on n vertices, with high probability every non-maximum matching has an augmenting path of length O(log n). This implies that augmenting path algorithms like the Hopcroft–Karp algorithm for bipartite graphs and the Micali–Vazirani algorithm for general graphs, which have a worst case running time of \(O(m\sqrt{n})\), run in time O(m log n) with high probability, where m is the number of edges in the graph. Motwani proved these results for random graphs when the average degree is at least ln(n) [Average Case Analysis of Algorithms for Matchings and Related Problems, Journal of the ACM, 41(6), 1994]. Our results hold, if only the average degree is a large enough constant. At the same time we simplify the analysis of Motwani.
47033631
Rank-maximal matchings
Suppose that each member of a set <i>A</i> of applicants ranks a subset of a set <i>P</i> of posts in an order of preference, possibly involving ties. A <i>matching</i> is a set of (applicant, post) pairs such that each applicant and each post appears in at most one pair. A <i>greedy</i> matching is one in which the maximum possible number of applicants are matched to their first choice post, and subject to that condition, the maximum possible number are matched to their second choice post, and so on. This is a relevant concept in any practical matching situation and it was first studied by Irving [8].We define the bipartite graph <i>G</i> = (<i>A U P,ε</i>), where ε consists of all pairs (<i>a, p</i>) such that post <i>p</i> appears in the preference list of applicant <i>a.</i> Each edge (<i>a, p</i>) has a rank <i>i</i>, which means that post <i>p</i> is an <i>i</i>th choice for applicant <i>a.</i> The traditional solution of computing a greedy matching in <i>G</i> would be to use the Hungarian algorithm to compute a maximum weight matching by assigning a suitably steeply decreasing sequence of weights to the edges. This would result in an algorithm with worst case running time <i>rn</i>(<i>m</i> + <i>n</i> log <i>n</i>) and the space requirement Θ(<i>rm</i>), where <i>n</i> is the number of vertices, <i>m</i> is the number of edges and <i>r</i> is the largest rank of an edge.Here, we describe two algorithms to compute a greedy matching that improve upon this algorithm. We give a combinatorial algorithm with running time <i>O</i>(min(<i>n</i> + <i>C,C</i>√<i>n</i>)<i>m</i>), where <i>C</i> ≤ <i>r</i> is the maximal rank of an edge used in a greedy matching. This algorithm works in phases and uses the maximum cardinality matching algorithm. We also give an <i>O</i>(<i>Cnm</i>) algorithm that tackles the problem of large edge weights introduced by the Hungarian algorithm. This algorithm uses scaling and works in phases. The space requirement of both these algorithms is <i>O</i>(<i>m</i>).
39971049
On Local Routing of Two-Terminal Nets
We showed that the local routing problem for two-terminal nets is solvable in quadratic time. There are three major open problems:
9321036
Matching Algorithms Are Fast in Sparse Random Graphs
AbstractWe present an improved average case analysis of the maximum cardinality
matching problem. We show that in a bipartite or general random graph on n
vertices, with high probability every non-maximum matching has an augmenting
path of length O(log n). This implies that augmenting path algorithms like
the Hopcroft-Karp algorithm for bipartite graphs and the Micali-Vazirani
algorithm for general graphs, which have a worst case running time of
O(m√n), run in time O(m log n) with high probability, where m is
the number of edges in the graph. Motwani proved these results for random
graphs when the average degree is at least ln (n) [Average Case
Analysis of Algorithms for Matchings and Related Problems, Journal of the
ACM, 41(6):1329-1356, 1994]. Our results hold if only the average degree is a
large enough constant. At the same time we simplify the analysis of Motwani.
6531885
TSP-based curve reconstruction in polynomial time
An instance of the curve reconstruction problem is a finite sample set V of an unknown curve V and the task is to connect the points in V in the order in which they lie on % Giesen [Gie99] showed recently tha t the Traveling Salesman tour of V solves the reconstruction problem under fairly week assumptions on V and V. We extend his result along three dimensions. We weaken the assumptions, we give an al ternate proof, and we show tha t in the context of curve reconstruction the Traveling Salesman tour can be constructed in polynomial time. 1 I n t r o d u c t i o n An instance of the curve reconstruction problem is a finite sample set V of an unknown curve -)' and the task is to construct a graph G on V such that two points in V are connected by an edge of G iff the points are adjacent on % The graph G is called a polygonal reconstruction of 7The curve reconstruction problem and the related surface reconstruction problem received a lot of at tention in the graphics and the computat ional geometry community. We are interested in reconstruction algorithms with guaranteed per/ormanc¢, i.e., a lgori thms which provably solve the reconstruction problem under certain assumptions on ~/ and V. Figure 1 i l lustrates the curve reconstruction problem. If the curve is closed, smooth, and uniformly sampled, several methods are known to work ranging over minimum spanning trees [FG94], a shapes [BB97, EKS83], B-skeletons [KR85], and r-regular shapes [Att97]. A survey of these techniques appears in [Ede98]. The case of non-uniformly sampled closed curves was first t reated successfully by Amenta, Bern and Eppstein [ABE98] and subsequently improved algorithms such as [DK99, Go199] appeared. Open nonuniformly sampled curves were treated in [DMR99]. All papers mentioned so far require that the underlying ~ a x c h partially supported by EG-projects ALCOM-IT and GALIA. tMax-Planck-Institute fiir Inforrnatik, Irn Stadtwald, 66123 Saarbr/icken $Max-Planck-Institute fiir Informatik, Irn Stadtwald, 66123 Saarbriicken . . 1. . ._.
9207249
Traveling Salesman-Based Curve Reconstruction in Polynomial Time
An instance of the curve reconstruction problem is a finite sample set V of an unknown collection of curves $\gamma$. The task is to connect the points in V in the order in which they lie on $\gamma$. Giesen [Proceedings of the 15th Annual ACM Symposium on Computational Geometry (SCG '99), 1999, pp. 207--216] showed recently that the traveling salesman tour of V solves the reconstruction problem for single closed curves under otherwise weak assumptions on $\gamma$ and V; $\gamma$ must be a single closed curve. We extend his result along several directions: 
we weaken the assumptions on the sample; we show that traveling salesman-based reconstruction also works for single open curves (with and without specified endpoints) and for collections of closed curves; we give alternative proofs; and we show that in the context of curve reconstruction, the traveling salesman tour can be constructed in polynomial time.
13864802
A Complete and Efficient Algorithm for the Intersection of a General and a Convex Polyhedron
A polyhedron is any set that can be obtained from the open halfspaces by a finite number of set complement and set intersection operations. We give an efficient and complete algorithm for intersecting two three-dimensional polyhedra, one of which is convex. The algorithm is efficient in the sense that its running time is bounded by the size of the inputs plus the size of the output times a logarithmic factor. The algorithm is complete in the sense that it can handle all inputs and requires no general position assumption. We also describe a novel data structure that can represent all three-dimensional polyhedra (the set of polyhedra representable by all previous data structures is not closed under the basic boolean operations).
28965703
Classroom Examples of Robustness Problems in Geometric Computations
The algorithms of computational geometry are designed for a ma- chine model with exact real arithmetic. Substituting floating point arithmetic for the assumed real arithmetic may cause implementations to fail. Although this is well known, there is no comprehensive documentation of what can go wrong and why. In this extended abstract, we study a simple incremental algorithm for planar convex hulls and give examples which make the algorithm fail in all pos- sible ways. We also show how to construct failure-examples semi-systematically and discuss the geometry of the floating point implementation of the orientation predicate. We hope that our work will be useful for teaching computational ge- ometry. The full paper is available at www.mpi-sb.mpg.de/˜mehlhorn/ ftp/ClassRoomExamples.ps. It contains further examples, more theory, and color pictures. We strongly recommend to read the full paper instead of this extended abstract.
17694660
Resource Constrained Shortest Paths
The resource constrained shortest path problem (CSP) asks for the computation of a least cost path obeying a set of resource constraints. The problem is NP-complete. We give theoretical and experimental results for CSP. In the theoretical part we present the hull approach, a combinatorial algorithm for solving a linear programming relaxation and prove that it runs in polynomial time in the case of one resource. In the experimental part we compare the hull approach to previous methods for solving the LP relaxation and give an exact algorithm based on the hull approach. We also compare our exact algorithm to previous exact algorithms and approximation algorithms for the problem.