title: Maximum median weight matching
body: <p>Finding a maximum total weight matching for a graph is a well studied problem.</p>
  
  <p>Is there any name and/or well defined algorithm for finding a maximal matching that maximizes its median weight instead ? (generalized to any other percentile).</p>
  
  <p>This problem got me when looking into matters of fairness of assignments.</p>
  
  <p>My lines of thought for possible solutions:</p>
  
  <ol>
  <li><p>Perhaps the weights can be somehow mapped to use the maximum total weight matching algorithm ? I find this unlikely</p></li>
  <li><p>Perhaps the maximum weight matching algorithm can be used repeteadly on different subgraphs in some fashion ?</p></li>
  <li><p>Solving the problem as an assignment problem using integer programming. But I wouldn't know how to express the median of the weights of the chosen set.</p></li>
  </ol>
  
  <p>In the case of bipartite graphs, <a href="http://research.nii.ac.jp/~uno/papers/isaac97web.pdf" rel="nofollow noreferrer">this</a> paper offers ways to find all maximal, maximum and perfect matchings. Then, if problem size allows, we can choose the matching with the desired properties with any kind of cost function.</p>
  
  <p>But I'm interested in the non-bipartite case. So, of course a biproduct of this question is: Do you know any implementation/algorithm that enumerates all maximal matchings of a graph ?</p>