Keyword: matching

Found 46 papers in total
3D-Hit: fast structural comparison of proteins on multicore architectures
3D-Hit: fast structural comparison of proteins on multicore architectures
2014,
3D‐Hit is a well established method for rapid detection of structural...
Robust recoverable perfect matchings
Robust recoverable perfect matchings
2015,
We study perfect matchings M in graphs G that have the two properties of being robust...
A novel approach to independent taxi scheduling problem based on stable matching
A novel approach to independent taxi scheduling problem based on stable matching
2014,
This paper describes a taxi scheduling system, which aims to improve the overall...
Succinct 2D Dictionary Matching
Succinct 2D Dictionary Matching
2013,
The dictionary matching problem seeks all locations in a given text that match any of...
The minimum maximal k‐partial‐matching problem
The minimum maximal k‐partial‐matching problem
2013,
In this paper, we introduce a new problem related to bipartite graphs called minimum...
Online bottleneck matching
Online bottleneck matching
2014,
We consider the online bottleneck matching problem, where k server‐vertices lie...
Exact Algorithms for Edge Domination
Exact Algorithms for Edge Domination
2012,
An edge dominating set in a graph G =( V , E ) is a subset of the edges D ⊆ E...
One‐to‐many non‐cooperative matching games
One‐to‐many non‐cooperative matching games
2013,
We study a strategic model of wage negotiations between firms and workers. First, we...
A Note on Roth's Consensus Property of Many‐to‐One Matching
A Note on Roth's Consensus Property of Many‐to‐One Matching
2013,
Roth (1985) claimed that (i) if each firm is allowed to select its most preferred...
Weighted inverse maximum perfect matching problems under the Hamming distance
Weighted inverse maximum perfect matching problems under the Hamming distance
2013,
Given an undirected network G ( V , E , c ) and a perfect matching M 0 , the inverse...
Almost Exact Matchings
Almost Exact Matchings
2012,
In the exact matching problem we are given a graph G , some of whose edges are colored...
Bipartite Matching in the Semi‐streaming Model
Bipartite Matching in the Semi‐streaming Model
2012,
We present the first deterministic 1+ ϵ approximation algorithm for finding...
Computing solutions for matching games
Computing solutions for matching games
2012,
A matching game is a cooperative game ( N , v ) defined on a graph G = ( N , E ) with...
A Randomized Algorithm for Approximate String Matching
A Randomized Algorithm for Approximate String Matching
2001,
We give a randomized algorithm in deterministic time O(N log M) for estimating the...
Uniquely Restricted Matchings
Uniquely Restricted Matchings
2001,
A matching in a graph is a set of edges no two of which share a common vertex. In this...
The pareto‐stability concept is a natural solution concept for discrete matching markets with indifferences
The pareto‐stability concept is a natural solution concept for discrete matching markets with indifferences
2011,
In a decentralized setting the game‐theoretical predictions are that only...
Retailer‐supplier matching: an application of the deferred acceptance algorithm
Retailer‐supplier matching: an application of the deferred acceptance algorithm
2011,
In this paper, we apply matching theory to supply chain coordination. We present...
String matching with inversions and translocations in linear average time (most of the time)
String matching with inversions and translocations in linear average time (most of the time)
2011,
We present an efficient algorithm for finding all approximate occurrences of a given...
Better and Simpler Approximation Algorithms for the Stable Marriage Problem
Better and Simpler Approximation Algorithms for the Stable Marriage Problem
2011,
We first consider the problem of finding a maximum size stable matching if incomplete...
A polynomial-time algorithm to find von Neumann-Morgenstern stable matchings in marriage games
A polynomial-time algorithm to find von Neumann-Morgenstern stable matchings in marriage games
2010,
This paper considers von Neumann-Morgenstern (vNM) stable sets in marriage games....
Faster algorithms for stable allocation problems
Faster algorithms for stable allocation problems
2010,
We consider a high-multiplicity generalization of the classical stable matching...
Two-stage stochastic matching and spanning tree problems: Polynomial instances and approximation
Two-stage stochastic matching and spanning tree problems: Polynomial instances and approximation
2010,
This article deals with the two-stage stochastic model, which aims at explicitly...
Total Dual Integrality of Rothblum's Description of the Stable-Marriage Polyhedron
Total Dual Integrality of Rothblum's Description of the Stable-Marriage Polyhedron
2008,
Rothblum showed that the convex hull of the stable matchings of a bipartite preference...
What Matchings Can Be Stable? The Testable Implications of Matching Theory
What Matchings Can Be Stable? The Testable Implications of Matching Theory
2008,
This paper studies the falsifiability of two–sided matching theory when agents'...
Papers per page: