Drop algorithm 's complexity

Drop algorithm 's complexity

Post by Hell » Sat, 03 May 2003 07:30:57



Drop algorithm:

Given T terminals and C concentrators and a center.  Concentrators are
connected directly to the center.

Step 1: Assign all terminals to the nearest concentor's site,e.g.,
connect terminal j to concentrator i will cost less than connecting
terminal j to other concentrators. Then connect terminal j to
concentrator i.

Step 2: For every concentrator j, we need to see that if we move the
concentrator away and connect the terminals to the center will save
some money. If that is the case, just move the concentrator away and
connect the terminals to the center.

The answer is TC^3.

 
 
 

Drop algorithm 's complexity

Post by James Waldb » Sat, 03 May 2003 22:21:07



> Drop algorithm:

> Given T terminals and C concentrators and a center.  Concentrators are
> connected directly to the center.

> Step 1: Assign all terminals to the nearest concentor's site,e.g.,
> connect terminal j to concentrator i will cost less than connecting
> terminal j to other concentrators. Then connect terminal j to
> concentrator i.

> Step 2: For every concentrator j, we need to see that if we move the
> concentrator away and connect the terminals to the center will save
> some money. If that is the case, just move the concentrator away and
> connect the terminals to the center.

> The answer is TC^3.

You haven't provided enough information about the "cost less" and
"save some money" relations for anyone else to verify an O(TC^3)
complexity.  If connection cost is proportional to distance and
concentrators are free and their locations are given, the complexity
is O(TC logC).  If you are trying to find optimal concentrator
locations to get a Steiner tree, that problem is NP-complete but
heuristics based on Prim or Kruskal have polynomial time.
-jiw

 
 
 

1. Calculating image 'complexity'

Hey all,

I've encountered a problem lately I just can't find a good solution to: How
to calculate complexity of an image? A simple solution is to find the
standard-deviation for every channel, and it's generally an okay solution,
but what if I have an image that 90% percents of it are solid, and the other
10% are noise. Standard deviation 'swallows' such cases. On the other hand,
the data I'm dealing with is not perfect imagery, there are some 'glitches'
(although very small - 1-2 pixel(s) ) - I want such occurrences to be
avoided.

What methods can you recommend? What should I be looking for?

Help much appreciated,
    Ofer.

2. System recommendations for Alias?

3. less complexity algorithm to find min and max values

4. Wanted Old computers you no longer want

5. how to know algorithm complexity

6. CD7.Why VERY slow file loading?

7. Complexity Analysis of Line Clipping Algorithms

8. <<<<<<<<<<<<How to make a laser being fired from a motion ship?>>>>>>>>>>>>>>>>>

9. algorithm complexity bullshit...

10. How to make a 'Drop Shadow'

11. Drag'n'Drop and DragImages