Given a complete bipartite graph on two sets of points containing n points each, in a bottleneck matching problem, we want to find an one-to-one correspondence, also called a matching, that minimizes the length of its largest edge; the length of an edge is simply the Euclidean distance between its end-points. As an application, consider matching taxis to requests while minimizing the largest distance between any request to its matched taxi. The length of the largest edge (also called the bottleneck distance) has numerous applications in machine learning as well as topological data analysis. One can use the classical Hopcroft-Karp (HK-) Algorithm to find the bottleneck matching. In this thesis, we consider the case where A and B are points that are generated uniformly at random from a unit square. Instead of the classical HK-Algorithm, we implement and empirically analyze a new algorithm by Lahn and Raghvendra (Symposium on Computational Geometry, 2019). Our experiments show that our approach outperforms the HK-Algorithm based approach for computing bottleneck matching. / Master of Science / Consider the problem of matching taxis to an equal number of requests. While matching them, one objective is to minimize the largest distance between a request and its match. Finding such a matching is called the bottleneck matching problem. In addition, this optimization problem arises in topological data analysis as well as machine learning. In this thesis, I conduct an empirical analysis of a new algorithm, which is called the FAST-MATCH algorithm, to find the bottleneck matching. I find that, when a large input data is randomly generated from a unit square, the FAST-MATCH algorithm performs substantially faster than the classical methods.

Thesis advisor: Utku M. Unver / The Market Design approach, which involves the creation of markets with desirable properties, has been successfully applied to study a wide range of real-world economic problems. The market design approach is helpful in scenarios where money can’t be used as a medium of exchange to facilitate transactions. The allocation of school/college seats to students, assigning residency positions to physicians, cadet-branch matching, and exchange of organs like kidneys and liver are some problems that have been successfully studied using the market design approach. Typically, the market design approach concerns with the setting up of two-sided markets with agents on each side of the market having preferences over each other or agents on one side and objects (school seats, military branches, public health goods like beds, ventilators, etc.) on the other side with agents having preferences over the objects and objects having priority over the agents. Priority ranking of agents can be considered an entitlement ranking where agents with higher priority have the right for the object compared to the agent with lower priority. The insights from the matching theory are then used to create a mechanism that matches agents with agents or objects for the given set of preferences/priority ranking satisfying desirable properties. Primary among these properties is stability, an equilibrium concept for matching. Stable matching ensures that matched agents/objects on the two sides of the market do not have an incentive to break up their respective matching and form a better matching for themselves. In the market design problem of matching agents to objects, stability ensures that the agent’s priority for objects is not violated. Other properties include strategy-proofness, where agents do not have an incentive to misreport their preferences. Strategy-proof mechanisms are simple and ensure that high-information agents cannot game the system at the expense of low-information agents. The priority ranking thus used in matching agents to objects has been subject to much criticism. The underlying process that generates the priority rankings can be inherently discriminatory. Exam scores are used to generate the priority ranking in allocating school seats to students. In the New York City school system, there has been a growing call for abolishing exams since it is considered to favor students with more resources. Similarly, the priority system used in the exchange of organs like kidneys and liver and triage allocation of scarce resources and services like hospital beds, vaccines, and ventilators has received much criticism. Triage protocols are developed with a utilitarian notion of maximum benefit given the constraints. This can result in people with better access to health care resources being better positioned under a triage protocol than those with lesser access. The dissertation comprises two essays, joint work with Kenzo Imamura where I study the pairwise kidney-exchange problem and a ventilator sharing problem where I study the triage allocation of ventilator slots under sharing. In the first essay, I consider the problem of allocating ventilator slots for sharing under a triage protocol that generates the priority order. The triage protocol is considered discriminatory since patients with better access to health care through their life cycle have a better chance to be placed ahead in the order when compared with patients with lesser access to healthcare services. I consider the allocation of ventilator slots under a system of reserves, where slots are set-aside for types of patients to address the shortcoming of the triage protocol. Sharing is possible between patients who are compatible. In addition to addressing the shortcomings of the generated priority order, I focus on the question of what respecting the generating priority order in a sharing environment means. In the second essay, we consider the pairwise-kidney exchange problem, where incompatible patient donor pairs are matched with each other subject to patient donor pairs being compatible with each other and acceptable to each other under a priority order. The priority order is generated using a composite score which includes variables like the area of patient donor location and post-transplant medical survivability, among other factors. In response to the concerns, two mechanisms have been developed in the literature for pairwise-kidney exchange, a mechanism that facilitates pairwise-kidney exchange under a strict priority order and an egalitarian mechanism that doesn’t have a priority ordering among compatible patients. Owing to the utilitarian nature of priority order ranking, the egalitarian mechanism has not been considered for adoption. We develop a compromise mechanism between the egalitarian mechanism and the mechanism which respects strict priority order. We show that the compromise mechanism carries forward nice properties like strategy-proofness, which incentivizes each patient-donor pair to reveal their complete set of compatible patient-donor pairs and bridges the concern of a need for priority order with egalitarianism. The predominant literature in Matching theory considers matching agents with agents/objects under a priority order considering all agents to be equal and the priority ordering to be the only difference in consideration among agents. My dissertation contributes to the matching literature where different agents can vary in ways other than the priority ordering, and we try to find solutions that strive to address the inequity. I thank my advisors for their generous advice and feedback in shaping my dissertation. / Thesis (PhD) — Boston College, 2022. / Submitted to: Boston College. Graduate School of Arts and Sciences. / Discipline: Economics.

No description available.

This thesis proposes an expressive yet efficient declarative framework for graph matching in constraint programming (CP), and focuses on efficient algorithms to solve the subgraph isomorphism problem. The framework is based on graph and map variables, and specific graph morphism constraints. This allows to model and solve various graph matching problems, avoiding the tedious development of dedicated and specific algorithms. A specialized filtering algorithm is proposed for the subgraph isomorphism problem, which uses the semantic of the problem as well as the global structure of the two input graphs. It is shown that it is the state-of-the-art filtering algorithm, compared to dedicated algorithms and other CP approaches. Various search techniques from CP are also extended to the subgraph isomorphism problem. An automatic detection and exploitation of symmetries for the subgraph isomorphism problem is proposed, together with a decomposition approach of the search. The significance of this thesis lies in the fact that, even though the framework is expressive, CP can be considered as the state-of-the-art for subgraph isomorphism, outperforming the dedicated known algorithms on current benchmarks.

Finding the maximum size of a matching in an undirected graph and finding the maximum size of branching in a directed graph can be formulated as matrix rank problems. The Tutte matrix, introduced by Tutte as a representation of an undirected graph, has rank equal to the maximum number of vertices covered by a matching in the associated graph. The branching matrix, a representation of a directed graph, has rank equal to the maximum number of vertices covered by a branching in the associated graph. A mixed graph has both undirected and directed edges, and the matching forest problem for mixed graphs, introduced by Giles, is a generalization of the matching problem and the branching problem. A mixed graph can be represented by the matching forest matrix, and the rank of the matching forest matrix is related to the size of a matching forest in the associated mixed graph. The Tutte matrix and the branching matrix have indeterminate entries, and we describe algorithms that evaluate the indeterminates as rationals in such a way that the rank of the evaluated matrix is equal to the rank of the indeterminate matrix. Matroids in the context of graphs are discussed, and matroid formulations for the matching, branching, and matching forest problems are given.

Existing service matching approaches trade precision for recall, creating the need for humans to choose the correct services, which is a major obstacle for automating the service matching and the service aggregation processes. To overcome this problem, the matchmaker must automatically determine the correctness of the matching results according to the defined users' goals. That is, only service(s)-achieving users' goals are considered correct. This requires the high-level functional semantics of services, users, and application domains to be captured in a machine-understandable format. Also this requires the matchmaker to determine the achievement of users' goals without invoking the services. We propose the G+ model to capture the high-level functional specifications of services and users (namely goals, achievement contexts and external behaviors) providing the basis for automated goal achievement determination; also we propose the concepts substitutability graph to capture the application domains' semantics. To avoid the false negatives resulting from adopting existing constraint and behavior matching approaches during service matching, we also propose new constraint and behavior matching approaches to match constraints with different scopes, and behavior models with different number of state transitions. Finally, we propose two correctness-aware matching approaches (direct and aggregate) that semantically match and aggregate semantic web services according to their G+ models, providing the required theoretical proofs and the corresponding verifying simulation experiments.

Feature matching in images plays an important role in computer vision such as for 3D reconstruction, motion analysis, object recognition, target tracking and dynamic scene analysis. In this paper, we present a robust cooperative strategy to establish the correspondence of the contours between two uncalibrated images based on the recovered epipolar geometry. We take into account two representations of contours in image as contour points and contour chains. The method proposed in the paper is composed of the following two consecutive steps: (1) The first step uses the LMedS method to estimate the fundamental matrix based on Hartley’s 8-point algorithm, (2) The second step uses a new robust cooperative strategy to match contours. The presented approach has been tested with various real images and experimental results show that our method can produce more accurate contour correspondences. / Singapore-MIT Alliance (SMA)

Weighted graph matching is a good way to align a pair of shapes represented by a set of descriptive local features; the set of correspondences produced by the minimum cost of matching features from one shape to the features of the other often reveals how similar the two shapes are. However, due to the complexity of computing the exact minimum cost matching, previous algorithms could only run efficiently when using a limited number of features per shape, and could not scale to perform retrievals from large databases. We present a contour matching algorithm that quickly computes the minimum weight matching between sets of descriptive local features using a recently introduced low-distortion embedding of the Earth Mover's Distance (EMD) into a normed space. Given a novel embedded contour, the nearest neighbors in a database of embedded contours are retrieved in sublinear time via approximate nearest neighbors search. We demonstrate our shape matching method on databases of 10,000 images of human figures and 60,000 images of handwritten digits.

Finding the maximum size of a matching in an undirected graph and finding the maximum size of branching in a directed graph can be formulated as matrix rank problems. The Tutte matrix, introduced by Tutte as a representation of an undirected graph, has rank equal to the maximum number of vertices covered by a matching in the associated graph. The branching matrix, a representation of a directed graph, has rank equal to the maximum number of vertices covered by a branching in the associated graph. A mixed graph has both undirected and directed edges, and the matching forest problem for mixed graphs, introduced by Giles, is a generalization of the matching problem and the branching problem. A mixed graph can be represented by the matching forest matrix, and the rank of the matching forest matrix is related to the size of a matching forest in the associated mixed graph. The Tutte matrix and the branching matrix have indeterminate entries, and we describe algorithms that evaluate the indeterminates as rationals in such a way that the rank of the evaluated matrix is equal to the rank of the indeterminate matrix. Matroids in the context of graphs are discussed, and matroid formulations for the matching, branching, and matching forest problems are given.

The main contents of this thesis are improving a UWB LNA, and analyze the input-matching, the noise, and the gain. First we use the feedback of the input transistor , and it different from the traditional source-degeneration inductor.The design can increase the gain and reduce the noise of the circuit.The second stage CS architecture designed to improve the overall gain of the circuit. Output level to use the source follower with the device even when the output matching . In the input matching,we use a shunt inductor and the impedance of the transistor itself to achieve high frequency matching. The UWB LNA dissipates 16.8 mW power and achieves input return loss (S11) -9.3 to -10 dB, output return loss (S22) -16.83 to -13 dB, forward gain (S21) 13.8 to 11.6 dB, reverse isolation (S12) below -30 dB, and noise figure (NF) of 2.38~3.31 dB over the 6~10 GHz band of interest. 1-dB compression point (P1dB) of -12.5 dBm and input third-order inter-modulation point (IIP3) of -2.5 dBm are achieved at 6 GHz.