On the exhaustiveness of truncation and dropping strategies in many-to-many matching markets

We consider two–sided many–to–many matching markets in which each worker may work for multiple firms and each firm may hire multiple workers. We study individual and group manipulations in centralized markets that employ (pairwise) stable mechanisms and that require participants to submit rank order lists of agents on the other side of the market. We are interested in simple preference manipulations that have been reported and studied in empirical and theoretical work: truncation strategies, which are the lists obtained by removing a tail of least preferred partners from a preference list, and the more general dropping strategies, which are the lists obtained by only removing partners from a preference list (i.e., no reshuffling). We study when truncation / dropping strategies are exhaustive for a group of agents on the same side of the market, i.e., when each match resulting from preference manipulations can be replicated or improved upon by some truncation / dropping strategies. We prove that for each stable mechanism, truncation strategies are exhaustive for each agent with quota 1 (Theorem 1). We show that this result cannot be extended neither to group manipulations (even when all quotas equal 1 – Example 1), nor to individual manipulations when the agent’s quota is larger than 1 (even when all other agents’ quotas equal 1 – Example 2). Finally, we prove that for each stable mechanism, dropping strategies are exhaustive for each group of agents on the same side of the market (Theorem 2), i.e., independently of the quotas.

Representing images by means of interval-valued fuzzy sets. Application to stereo matching

Stereo matching tries to find correspondences between locations in a pair of displaced images of the same scene in order to extract the underlying depth information. Pixel correspondence estimation suffers from occlusions, noise or bias. In this work, we introduce a novel approach to represent images by means of interval-valued fuzzy sets to overcome the uncertainty due to the above mentioned problems. Our aim is to take advantage of this representation in the stereo matching algorithm. The image interval-valued fuzzification process that we propose is based on image segmentation in a different way to the common use of segmentation in stereo vision. We introduce interval-valued fuzzy similarities to compare windows whose pixels are represented by intervals. In the experimental analysis we show the goodness of this representation in the stereo matching problem. The new representation together with the new similarity measure that we introduce shows a better overall behavior with respect to other very well-known methods.

Applying machine learning to catalogue matching in astrophysics

We present the results of applying automated machine learning techniques to the problem of matching different object catalogues in astrophysics. In this study, we take two partially matched catalogues where one of the two catalogues has a large positional uncertainty. The two catalogues we used here were taken from the H I Parkes All Sky Survey (HIPASS) and SuperCOSMOS optical survey. Previous work had matched 44 per cent (1887 objects) of HIPASS to the SuperCOSMOS catalogue. A supervised learning algorithm was then applied to construct a model of the matched portion of our catalogue. Validation of the model shows that we achieved a good classification performance (99.12 per cent correct). Applying this model to the unmatched portion of the catalogue found 1209 new matches. This increases the catalogue size from 1887 matched objects to 3096. The combination of these procedures yields a catalogue that is 72 per cent matched.

Prospective Estimation of Organ Dose Prior to Examination: Matching Patient to Digital Phantoms

Prospective estimation of patient CT organ dose prior to examination can help technologist adjust CT scan settings to reduce radiation dose to patient while maintaining certain image quality. One possible way to achieve this is matching patient to digital models precisely. In previous work, patient matching was performed manually by matching the trunk height which was defined as the distance from top of clavicle to bottom of pelvis. However, this matching method is time consuming and impractical in scout images where entire trunk is not included. Purpose of this work was to develop an automatic patient matching strategy and verify its accuracy.

Edge enhancement improves disruptive camouflage by emphasising false edges and creating pictorial relief

Disruptive colouration is a visual camouflage composed of false edges and boundaries. Many disruptively camouflaged animals feature enhanced edges; light patches are surrounded by a lighter outline and/or a dark patches are surrounded by a darker outline. This camouflage is particularly common in amphibians, reptiles and lepidopterans. We explored the role that this pattern has in creating effective camouflage. In a visual search task utilising an ultra-large display area mimicking search tasks that might be found in nature, edge enhanced disruptive camouflage increases crypsis, even on substrates that do not provide an obvious visual match. Specifically, edge enhanced camouflage is effective on backgrounds both with and without shadows; i.e. this is not solely due to background matching of the dark edge enhancement element with the shadows. Furthermore, when the dark component of the edge enhancement is omitted the camouflage still provided better crypsis than control patterns without edge enhancement. This kind of edge enhancement improved camouflage on all background types. Lastly, we show that edge enhancement can create a perception of multiple surfaces. We conclude that edge enhancement increases the effectiveness of disruptive camouflage through mechanisms that may include the improved disruption of the object outline by implying pictorial relief.

Belief propagation for minimum weight many-to-one matchings in the random complete graph

In a complete bipartite graph with vertex sets of cardinalities n and n', assign random weights from exponential distribution with mean 1, independently to each edge. We show that, as n -> infinity, with n' = n/alpha] for any fixed alpha > 1, the minimum weight of many-to-one matchings converges to a constant (depending on alpha). Many-to-one matching arises as an optimization step in an algorithm for genome sequencing and as a measure of distance between finite sets. We prove that a belief propagation (BP) algorithm converges asymptotically to the optimal solution. We use the objective method of Aldous to prove our results. We build on previous works on minimum weight matching and minimum weight edge cover problems to extend the objective method and to further the applicability of belief propagation to random combinatorial optimization problems.

A constraint to improve the reliability of stereo matching using the rank transform

The rank transform is a non-parametric technique which has been recently proposed for the stereo matching problem. The motivation behind its application to the matching problem is its invariance to certain types of image distortion and noise, as well as its amenability to real-time implementation. This paper derives an analytic expression for the process of matching using the rank transform, and then goes on to derive one constraint which must be satisfied for a correct match. This has been dubbed the rank order constraint or simply the rank constraint. Experimental work has shown that this constraint is capable of resolving ambiguous matches, thereby improving matching reliability. This constraint was incorporated into a new algorithm for matching using the rank transform. This modified algorithm resulted in an increased proportion of correct matches, for all test imagery used.

An Evidential Approach to Query Interface Matching on the Deep Web

Matching query interfaces is a crucial step in data integration across multiple Web databases. The problem is closely related to schema matching that typically exploits different features of schemas. Relying on a particular feature of schemas is not suffcient. We propose an evidential approach to combining multiple matchers using Dempster-Shafer theory of evidence. First, our approach views the match results of an individual matcher as a source of evidence that provides a level of confidence on the validity of each candidate attribute correspondence. Second, it combines multiple sources of evidence to get a combined mass function that represents the overall level of confidence, taking into account the match results of different matchers. Our combination mechanism does not require use of weighing parameters, hence no setting and tuning of them is needed. Third, it selects the top k attribute correspondences of each source attribute from the target schema based on the combined mass function. Finally it uses some heuristics to resolve any conflicts between the attribute correspondences of different source attributes. Our experimental results show that our approach is highly accurate and effective.

Boston, Massachusetts Region LIDAR First Return Elevation Data, 2002

LIDAR (LIght Detection And Ranging) first return elevation data of the Boston, Massachusetts region from MassGIS at 1-meter resolution. This LIDAR data was captured in Spring 2002. LIDAR first return data (which shows the highest ground features, e.g. tree canopy, buildings etc.) can be used to produce a digital terrain model of the Earth's surface. This dataset consists of 74 First Return DEM tiles. The tiles are 4km by 4km areas corresponding with the MassGIS orthoimage index. This data set was collected using 3Di's Digital Airborne Topographic Imaging System II (DATIS II). The area of coverage corresponds to the following MassGIS orthophoto quads covering the Boston region (MassGIS orthophoto quad ID: 229890, 229894, 229898, 229902, 233886, 233890, 233894, 233898, 233902, 233906, 233910, 237890, 237894, 237898, 237902, 237906, 237910, 241890, 241894, 241898, 241902, 245898, 245902). The geographic extent of this dataset is the same as that of the MassGIS dataset: Boston, Massachusetts Region 1:5,000 Color Ortho Imagery (1/2-meter Resolution), 2001 and was used to produce the MassGIS dataset: Boston, Massachusetts, 2-Dimensional Building Footprints with Roof Height Data (from LIDAR data), 2002 [see cross references].

Boston, Massachusetts, 2-Dimensional Building Footprints with Height Data (from LIDAR data), 2002

This dataset consists of 2D footprints of the buildings in the metropolitan Boston area, based on tiles in the orthoimage index (orthophoto quad ID: 229890, 229894, 229898, 229902, 233886, 233890, 233894, 233898, 233902, 237890, 237894, 237898, 237902, 241890, 241894, 241898, 241902, 245898, 245902). This data set was collected using 3Di's Digital Airborne Topographic Imaging System II (DATIS II). Roof height and footprint elevation attributes (derived from 1-meter resolution LIDAR (LIght Detection And Ranging) data) are included as part of each building feature. This data can be combined with other datasets to create 3D representations of buildings and the surrounding environment.