47415035
Polynomial and Abstract Subrecursive Classes
The reducibility ''polynomial time computable in'' for arbitrary functions isintroduced. It generalizes Cook's definition from sets to arbitrary functions. A complexity-theoretic as well as a syntactic characterization is given and their equivalence is shown. This equivalence and the naturalness of both definitions give evidence that our notion is ''correct.'' The computable functions are classified into polynomial classes according to this reducibility. The ordering of these classes under set inclusion is studied. Honest classes are introduced and using them, the classification is related to the computational complexity of the functions classified. The algebraic structure of honest classes is also investigated. In Section II abstract subrecursive reducibilities are introduced. An axiomaticdefinition in purely recursion-theoretic terms is given; in particular, no reference to a particular machine model is needed. The definition is in the spirit of Strong's and Wagner's characterizations of basic recursive function theories. All known reducibilities are abstract reducibilities. The algebraic structure of abstract classes is explored.
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.
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>).
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.
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.
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.
8848693
Look — a Lazy Object-Oriented Kernel for geometric computation
In this paper we describe and discuss a new kernel design for g eometric computation in the plane. It combines different kin ds of floating-point filter techniques and a lazy evaluation schem e with the exact number types provided by LEDA allowing for efficien t and exact computation with rational and algebraic geometri c objects. It is the first kernel design which uses floating-point filter t chniques on the level of geometric constructions. The experiments we present – partly using the CGAL framework – show a great improvement in speed and – maybe even more important for practical applications – memory consumption when dealing with more complex geometric computations.
12636571
Curve reconstruction: connecting dots with good reason
Curve reconstruction algorithms are supposed to reconstruct curves from point samples. Recent papers present algorithms that come with a guarantee: Given a sufficiently dense sample of a closed smooth curve, the algorithms construct the correct polygonal reconstruction. Nothing is claimed about the output of the algorithms, if the input is not a dense sample of a closed smooth curve, e.g., a sample of a curve with endpoints. We present an algorithm that comes with a guarantee for any setP of input points. The algorithm constructs a polygonal reconstruction G and a smooth curve that justifies G as the reconstruction fromP . © 2000 Elsevier Science B.V. All rights reserved.
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).
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.