Projects Course – Geometric Algorithms 202-1-4141
Fall 2004

Prerequisite: Algorithms




Matya Katz  (

Office hours: TBA, Deichmann building (58), room 315, Tel: (08) 6461628


Teaching Assistant:

Office hours:


Class Time:

Wednesday 12-14 (building 28, room 301)

Course Description:

Several projects will be offered dealing with power assignment (alternatively, range assignment) in radio networks. Let P be a set of n points in the plane, representing n transmitters-receivers (or transmitters for short). In the general version of the power assignment problem one needs to assign transmission ranges to the transmitters in P, so that  (i) the resulting communication graph is strongly connected; that is, for any two transmitters p1 and  p2 in P, there exists a sequence of transmitters (i.e., a path) p1=q1,q2,…,qk=p2, such that q2 is within range r(q1) from q1, q3 is within range r(q2) from q2, etc., where r(qi) is the range that was assigned to qi, and  (ii) the total power consumption (i.e., the cost of the assignment of ranges) is minimized, where the total power consumption is a function of the form sum_{p in P} r(p)^a, where a is a constant typically between 2 and 5. The general version of the power assignment problem is known to be NP-hard, and the best approximation that is known is a 2-approximation.


In practice, though, it is usually impossible to assign arbitrary power levels (ranges) to the transmitters of a radio network. Instead one can only choose from a small number of preset power levels, corresponding to a small number of ranges. We refer to this more realistic version of the power assignment problem as the power assignment problem with c power levels (where c > 1 stands for a small constant number).


In a typical project, the students will have to develop and implement algorithms and/or heuristics for efficiently solving one of several variants of the power assignment problem.



Below is a selection of papers dealing with the power assignment problem from a theoretical point of view. For some of the projects, it might be helpful to ``peek'' at one or more of these papers.


L. M. Kirousis, E. Kranakis, D. Krizanc, and A. Pelc.

Power consumption in packet radio networks.

14th Annual Sympos. Theoretical Aspects of Computer Science (STACS), 1997, 363-374, LNCS 1200.


Paper on the minimum energy broadcast tree problem (to be added).


P. Carmi and M.J. Katz.

Power assignment in radio networks with two power levels.

Proc. 9th Scandinavian Workshop on Algorithm Theory, 2004, 431—441, LNCS 3111.



Last update: August 23, 2004