Skip to content


A max-min fairness algorithm

Max-min fairness is a useful concept in communications.

A friend of mine recently wanted me to write an algorithm which can be used to select communication links with max-min fairness for multiple users. I thought it might be useful/interesting for some.

Problem: Select an element from each row of a given matrix, maximizing the minimum value (max-min fairness), under the constraint that no two elements should be from the same row.

MATLAB implementation: m-file

Example call of the function in MATLAB:

Nr = 3;
Nc = 4;
mat = abs(randn(Nr,Nc));
Y = maxminfair(mat);

Use: This is useful in problems like assigning users communication links, under a constraint that some links can be used by only a single user at a given time. Or when finding minimum cost paths for few users simultaneously, when some links in the graph can be taken by only one user at a time.

Note: The matrix passed to the function should have all elements real and positive. (It can be generalized, but I did not want it for my problem, as all the elements were energy quantities)
If the matrix you need to use has zero or negative elements, pass ‘mat – min(min(mat))+1‘ instead and add ‘min(min(mat)) – 1‘ to the final answer.

If there are any bugs in the algo, or any improvements that can/must be made, do let me know.

Posted in Interests. Tagged with , .

Point Reyes

Point reyes

Point Reyes

This was taken at Point Reyes, while I was away in a road trip in California over my Christmas vacation with my sister and a couple of friends. I was excited to visit the beautiful Yosemite and Grand Canyon. We passed Death valley, Las Vegas, San Diego and LA on the way, and stayed with my friend Omar’s lovely family at El Centro in Christmas eve.

I came back to Edmonton last week, and started the winter term at uni this Monday (10th). It’s going to be an exciting term, with the instructor work, conference travel and everything. Looking forward!

Posted in Photography. Tagged with .

A brain-teaser from spiked math

An interesting brain-teaser from Spiked math. :)

An extension of the problem can be found here, which I couldn’t try yet.

Posted in Puzzles. Tagged with , .

The heavier pool ball

There are 9 pool balls(A,B,..,I), one of which is heavier than the rest.
You are given a balance, which will show which side is heavier than the other, or whether they have equal weight.

a) How many time would you need to use the scale, in order to find out which ball is heavier?
b)

You are given the additional information, that

  • probability of A being heavier is 1/3.
  • probability of B,C being heavier is 1/6 each.
  • Probability of C,D,..,I being heavier is 1/18 each.

We can use this information to reduce the expected number of weighing that is required to find the heavier ball.

What is the new expected number of uses of the balance required? (and state what the respective weighing strategy is)
c) Generalize for the case when one ball could be either heavier or lighter, out of N pool balls and any pmf.

Expected number of uses = Sum of “number of uses for an outcome X probability of an outcome”, over all outcomes.
(Outcome = the event of one particular ball being heavier)

Useful links:
Entropy  – http://en.wikipedia.org/wiki/Entropy_%28information_theory%29
http://en.wikipedia.org/wiki/Huffman_coding

Posted in Puzzles. Tagged with , .

The flow

The flow

This is a small stream connecting the upper Grassi lake and lower Grassi lake.

Grassi lake trail is a relatively easy hike, which takes only couple of hours for a round trip. You can find more details here.

The trail divides in to two routes, ‘easy’ and ‘more difficult’. The more difficult route is recommended as you’ll experience the beautiful view of the water fall and Ha Ling peak.

Posted in Photography.

Quarry Lake, Canmore

Quarry lake, Canmore

This a small lake you will find in Canmore, Alberta. This is an artificial lake made out of an old mining area, and is claimed to be a good example of how the adverse environmental effects from mining can be minimized.
It is a beautiful place to visit, if you are in Canmore, or on your way to Banff.

Posted in Photography. Tagged with , .

Building houses, a puzzle from mathsnet.net

I recently stumbled upon these really cool puzzles, at mathsnet (http://mathsnet.net/geometry/solid/houses.html)
It’s quite interesting and a fun change from the regular work.
So, give your brain a treat, and try those puzzles. :-)

If you found it hard, I have few tips and a little strategy below.

I tried some of those puzzles and though of a simple strategy that would make things easier.

  1. Fill up the whole cube.
  2. Remove all must be removed – from the empty position in the views, we can decide which blocks must be removed.
  3. Mark which blocks MUST stay.
  4. Are there any block that should be definitely removed?
    • yes -> remove all such blocks *
    • no -> remove an unmarked block at random **
  5. Is numebr of blocks higher than the target?
    • yes -> go to step 3
    • no -> Stop

Fig1:figuur1 target

* Identifying blocks that should definitely be removed:

When deciding what block to remove, it is important first to identify how many redundancies there are in each plane.

Forexample, in figuur1 (problem 1 ), you can see that all the views (front, right, top) has 12 blocks each(Fig1), and the number of available blocks to build it is also 12. Hence, we know, there are no redundant blocks in any plane. i.e. no 2 blocks are sharing the same line.

In figuur3, we can see that front, right views has 12 blocks each, while top view has ony 8 blocks (Fig2).

Fig2:figuur3 target

Hence, we identify that none of the blocks should be sharing any horizontal lines, but there would be more than one block sharing some vertical lines.So, if there are any blocks that are marked as ‘must stay’ is sharing such a line(where there should be no redundant blocks) with an unmarked block, we know the unmarked block should definitely be removed.

**Due to the symmetry of the problem, if there aren’t any blocks that should definetely be removed, randomly removing an unarked block would not affect the solution.

I found this method of filling the cube and breaking it up afterwards easier than filling it up to match the views.

Solving figuur3, with screen-shots explaining the strategy.

1.

2.

3. The blocks marked with a black dot are the ones that should definitely stay.

4.

In this figure, the block that was in the square marked in a black cross was removed. (at random).

You can see how this introduced new blocks that MUST stay. (marked with red dots). (step 3 , in 2nd iteration)

And as discussed earlier, since there shouldn’t be any redundant blocks in the horizontal plane, the blocks marked in red crosses should be removed.(step 4, in 2nd iteration)

By continuing this method, you can achieve at the final target, with 12 cubes. :)

Many thanks to mathsnet.net for the cool puzzles!!!

Posted in Puzzles. Tagged with , .

As happy as a lark…

As happy as a lark...

As happy as a lark
chirping around
dawn to dusk,
keeping myself bound,
in an endless chant.
Worried,
if I stop
would silence take over.

The silence,
the unbearable stillness,
broken,
only by the eeriness
of a distant echo.
Shrieking the loneliness,
of a forgotten melody
relished no more

A forgotten melody
in a murmur off-key,
reminding,
the certain mortality,
questioning out loud
the rationale of the singing.
And louder I sing,
cobbling up a tune.

And louder I sing,
as happy as a lark.

Posted in Photography, Scribbles.

Green, Oh! how much I miss thee.

Taken when traveling along Highway 2 from Edmonton to Calgary,  in Summer 2010.

Posted in Photography.

In to the darkness

In to the darkness...

Captured at the Hawrelak park, Edmonton.

A goose swimming by itself, at the sunset.

Posted in Photography.