Optimizing Wi-Fi Network Frequencies with Graph Theory

[brojesus111]

Homework Statement

There are n amount of wi-fi networks in a given neighborhood. For every pair that are within 50 yards, the frequency used must be different, otherwise there will be interference. How few frequencies are required so that every wi-fi network can be assigned a frequency without interference? Express this problem as a graph theoretic optimization problem.

The Attempt at a Solution

So I believe I can turn this into a k-colorable problem in which the networks are the vertices and the edges are the pairs within 50 yards. Then find the smallest k for which this graph would be k-colorable.

I'm wondering if there is a way express this in a more mathematical manner, with an objective function and with constraints. Maybe an integer program? I'm not quite sure. Any help is much appreciated.

 

[haruspex]

Your answer looks fine to me. You're not asked to propose an algorithm to solve it.

 

[Ray Vickson]

Homework Statement

There are n amount of wi-fi networks in a given neighborhood. For every pair that are within 50 yards, the frequency used must be different, otherwise there will be interference. How few frequencies are required so that every wi-fi network can be assigned a frequency without interference? Express this problem as a graph theoretic optimization problem.

The Attempt at a Solution

So I believe I can turn this into a k-colorable problem in which the networks are the vertices and the edges are the pairs within 50 yards. Then find the smallest k for which this graph would be k-colorable.

I'm wondering if there is a way express this in a more mathematical manner, with an objective function and with constraints. Maybe an integer program? I'm not quite sure. Any help is much appreciated.

There are such formulations; see, eg., http://www.maths.ed.ac.uk/~jmarecek/timetabling/asap2007-slides.pdf or
http://www.cs.amherst.edu/~ccm/cs34/papers/dias.pdf .

 

[brojesus111]

Your answer looks fine to me. You're not asked to propose an algorithm to solve it.

Ok, I have another question if you don't mind.

Problem: Say that there is a parking lot and there are n amount of cars. For each pair of cars, if they go to the same parking spot at the same time then they would need different spots. How few parking spots are required to hold all the cars?

Is this problem also looking for the chromatic number?

In this case, the cars are the vertices and the edges connecting the pairs would be the ones that go to the same parking spot at the same time. And then you would just look for the smallest k for which the graph is k-colorable. Is this right?

Thanks!

 

[haruspex]

Ok, I have another question if you don't mind.

It's better to start a new thread.

Problem: Say that there is a parking lot and there are n amount of cars. For each pair of cars, if they go to the same parking spot at the same time then they would need different spots. How few parking spots are required to hold all the cars?

I don't understand the set-up. Are there some restriction on which cars can go in which spots? Is there another level in here, like groups of spots within the lot? I assume a spot takes one car.

 

[brojesus111]

It's better to start a new thread.

I don't understand the set-up. Are there some restriction on which cars can go in which spots? Is there another level in here, like groups of spots within the lot? I assume a spot takes one car.

There is no restriction regarding which cars can go in which spots, just that a spot can only take one car. No groups of spots within the lot.

I think a clearer question would be with boats.

There are boats that dock in a certain port. For each pair of boats, if they are in the port at the same time then they would need different docks. How few docks are needed to hold all the boats?

 

[haruspex]

There is no restriction regarding which cars can go in which spots, just that a spot can only take one car. No groups of spots within the lot.

I think a clearer question would be with boats.

There are boats that dock in a certain port. For each pair of boats, if they are in the port at the same time then they would need different docks. How few docks are needed to hold all the boats?

Why isn't it just equal to the number of cars/boats?

 

[brojesus111]

Why isn't it just equal to the number of cars/boats?

I don't think all the boats are always in the port at the same time, so you're trying to optimize how few you would need. Similar to the last problem, you could have as many frequencies as there are wifi-networks, but you want to minimize it such that you only add a new one when there is a conflict.

I know for a fact that the answer to this question is either find the min vertex cover, min edge cover, or the min chromatic number. I couldn't think of a way where it's the other two, so I assumed it is the min chromatic number since it seems similar to the last problem. You create an edge when there is a conflict and find the minimum chromatic number. So in this case create an edge for any pair of cargo ships in the same port at the same time and then solve for the min chromatic number.

Edit: So I think we can make this into a small example. Let's say 3 boats are in the port at the same time.

We can see clearly that we would need 3 docks. The chromatic number would be 3, the vertex cover would be 2, and the edge cover would be 2 (think of a triangle). Thus for this problem we need to be solving for the min chromatic number.

I think it is essentially the same problem. Swap wi-fi networks for boats, "within 50 yards" to "in the port at the same time", and we are looking for a minimum amount in both.

 

[haruspex]

I think it is essentially the same problem. Swap wi-fi networks for boats, "within 50 yards" to "in the port at the same time", and we are looking for a minimum amount in both.

No, it's different, unless there is some relationship between specific boats. If there are N equivalent boats but never more than R in port at one time then R berths suffice.
Is this a problem you've been given? If so, what's the exact wording?

 

[brojesus111]

No, it's different, unless there is some relationship between specific boats. If there are N equivalent boats but never more than R in port at one time then R berths suffice.
Is this a problem you've been given? If so, what's the exact wording?

There are boats that dock in a certain port. For each pair of these boats, if they are in the port at the same time, then they will require different docks. How few docks are needed to hold all the boats? Express this problem as a graph theoretic optimization problem.

The car example was another question that our TA said was identical to the boat problem.

The hint was that this is a minimization problem, and the TA for the course said it is between the three we have covered in class: min vertex cover, min edge cover, and min chromatic number.

 

[haruspex]

There are boats that dock in a certain port. For each pair of these boats, if they are in the port at the same time, then they will require different docks. How few docks are needed to hold all the boats? Express this problem as a graph theoretic optimization problem.

The car example was another question that our TA said was identical to the boat problem.

The hint was that this is a minimization problem, and the TA for the course said it is between the three we have covered in class: min vertex cover, min edge cover, and min chromatic number.

OK, but that does seem to be a trivial problem. The answer is obviously equal to the total population of boats. You can certainly express it as a chromatic number problem by using colours for the berths, but the graph for N boats is simply K_N, making the minimum colours N. Equally it can be expressed as a min vertex cover - do you see how? (Hint: the graph is just as trivial, if not more so.)

 

[brojesus111]

OK, but that does seem to be a trivial problem. The answer is obviously equal to the total population of boats. You can certainly express it as a chromatic number problem by using colours for the berths, but the graph for N boats is simply K_N, making the minimum colours N. Equally it can be expressed as a min vertex cover - do you see how? (Hint: the graph is just as trivial, if not more so.)

Yes, I see what you mean. The way I have it set up as the chromatic number will always have it be a clique of the total number of boats since every pair is adjacent to each other (thus when doing the coloring problem, it will just be the total number of boats).

Is the min vertex problem just having the vertices be the ships in that port with no edges?

 

[haruspex]

Is the min vertex problem just having the vertices be the ships in that port with no edges?

Yes.