2
$\begingroup$

Given $n$ people, $k$ out of which own a car. We need to match a car for each person without a car. Conditions:

  • Each car fits $5$ people, including the driver.
  • Each driver will only allow his friends to ride with him.

I am looking for an algorithm to determine if there is a match. i.e. everyone gets to ride.

I am not seeking complete answer. Hints/pointers should suffice since this is part of my college assignment.

Thank you.

$\endgroup$
2
$\begingroup$

This might be an extension of the marriage theorem, except that any group of n passengers needs to be friends with at least $\left \lceil \frac{n}{4}\right \rceil$ drivers.

$\endgroup$
  • $\begingroup$ Am I looking for a Stable Matching algorithm for a bigraph of unequal sets? $\endgroup$ – Airwavezx Jan 27 '15 at 16:43
  • $\begingroup$ @Airwavezx Yes, I think it might be a bit like the hospital/resident problem. $\endgroup$ – Joffan Jan 27 '15 at 16:45
  • $\begingroup$ Your hint helped me understand and reach the answer. The condition I used for the algo: For all subsets of drivers this condition should be met: 4 times the size of the subset should be smaller or equal to the size of its neighboring vertices. $\endgroup$ – Airwavezx Jan 27 '15 at 18:48
0
$\begingroup$

A linear programming formulation should do nicely, the Integrality Theorem guaranteeing that basic feasible solutions are in integers.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.