Diary, June 2001

 
   Sun Mon Tue Wed Thu Fri Sat
                         1   2
     3   4   5   6   7   8   9
    10  11  12  13  14  15  16
    17  18  19  20  21  22  23
    24  25  26  27  28  29  30

Friday, June 1, 2001

An optimalisation problem

In my work, I encountered an optimalisation problem, which can be described as follows:

  Sum { Max { T(e,v) 
            | e in E and M(e) = v 
            }
      | v in { M(e) | e in E }
      }

I thought some time about an algorithm that would find a mapping meeting the requirement, or at least one that would come very close. I had some kind of feeling that this might be a NP-complete problem. After some thinking, I though that I had found a good algorithm. It looks like this:

Start with a mapping M₀ such that:

   And { T(e,M₀(e)) <= Min { T(e,v) | v in V }  
       |  e in E }

Given a mapping M_n see if there is a mapping M_n+1, that differs for one value of E, and that is better. If such a mapping exists, repeat this step.

I thought that this was quite a good algorithm that would quickly find a (near) optimal solution. And I still think it does for the problem domain from which it was derived from. However, this morning, I discovered that it is indeed a NP-complete problem. One way of proving that a certain problem is NP-complete is by proving that it is a superset of another NP-complete problem. I realized that the problem described here is a superset of the Minimum Vertex Cover. To show this, I have to proof that each Minimum Vertex Cover problem can be mapped onto a problem like the one described here. Now, that is not so difficult. The Minimum Vertex Cover for a graph G(E,V) can be mapped on the problem described here, by defining the function T such that T(e,v) equal to 1 if the vertex v is on of the end points of the edge e, and otherwise equal to infinitive. It is obvious that each mapping M defines the vertex cover { M(e) | e in E }. The value of the expression that needs to be minimized equals to the number of elements in the vertex cover. Finding a mapping for which the value of the expression is minimal, is thus equivalent with finding the Minimum Vertex Cover.

The algorithm which I proposed is thus rather useless in some typical cases. For those typical cases, in both steps there are just many mappings to choose from. It might be the case that the algorithm does work good, if always only one mapping can be chosen in each step. During the algorithm one can tell something about how well the algorithm performs based on all the values for the expression that are found for all mappings that are being searched.

Monday, June 4, 2001

Andy can bike

Yesterday evening, my mother went walking with Andy on his tree-wheeler. She had to push him all the time, as he refused to do anything himself. We have been pushing him around for more than a year now. My father had attached some shoe holders onto the peddles, such that we could strap his shoes to the peddles.

Tonight, Annabel came to call me. Li-Xia had gone out walking with Andy. There outside on the street I saw how Andy could now bike by himself. I looked as he finally understood what biking is all about. He was biking around as fast as he could. Of course, I immediately phoned my mother to tell her the good news.

Friday, June 15, 2001

Sending a video tape

Today, we sent a tape about Andy's eating behaviour to the "Winckelsteegh" with a short note. The tape also contained some recordings made on the daycare center were Andy is going every day, which really surprised us, because he was eating there almost without any problems at all, and even cooperating a little. This really astonished us.

(follow-up)

Sunday, June 17, 2001

Revival and prosecution

We had some one from Open Doors preaching today. Open Doors is an organisation that works amongh the prosecuted church. He reminded us that in more than 60% of the world Christians are prosecuted for their faith. That means that we are living in the small part where we are still free to practice our religion. This speaker told how they some years ago told the Christians of some countries that they should prepare for prosecution, and that these Christians were simply saying that there was not going to be any prosecution in their countries. But the reality is now that they are being prosecuted in their countries!

He furthermore stated, that also in our country we could encounter prosecution. That it is a reality that our government is no longer considering religion an important issue. And indeed, we are living in an atheistic country.

But his most important statement was that church history has told us that revival and prosecution often go hand in hand. We should not think that because every thing is so peacefull in our country, that God will spare us the prosecution. But maybe He will also give us a revival at the same time!

(follow-up)

Pulling out a tooth

Today, Annabel had bumped against something with her loose tooth. This evening, when standing in the bathroom, I saw that the tooth was now indeed very loose, and I told Annabel to pull it out. She pushed a little, and indeed her tooth came out.

Wednesday, June 20, 2001

Ear tubes

This morning, I took Andy to the hospital because he needed new tubes in his ears. This will be his third set of ear tubes. Last week his ENT had noticed that one ear did not have a tube anymore. He did not bother to check the other ear, because Andy was giving a lot of trouble. Andy was the first one this morning. When I brought him into the room, he started to cry, but soon after the had put the cap over his mouth, he fell asleep. When he woke up, he was quite confused, and wanted me to scratch his neck and back. He often wants us to scratch him there, so it was nothing strange in itself. But he kept on complaining. Only when the brought in the next child, he suddenly watched her with interest, and he became quiet. Not much later we went home. I also got a box with the old ear tube that was still present in the other ear.

hundred digits in ten minutes

This afternoon, I found a note with the first hundred digits of pi. I told my colleagues that I had learned them by heart before, and that it was not so difficult at all. I told them I could learn them by heart again in ten minutes. I did this while I walked to the restrooms. And indeed I only made three mistakes when I wrote them down ten minutes later.

Tuesday, June 26, 2001

Power failure

Around 11:34 in the morning, we had a very short power dip, enough to make all computers and file servers to reboot. Around a quarter past twelve, it was announced that it would still take several ours before one of hour major file servers will be available again.

(previous and next.)

Home | May 2001 | July 2001.