Nelson MORALES VARELA

I'm doing my PhD in the MASCOTTE, a I3S/CNRS/INRIA joint team. Most of the team (includying me) is located at the INRIA research unit of Sophia-Antipolis. I work in approximation algorithms for telecommunication problems. Briefly speaking, this means that the problems we try to solve are motivated by applications coming from telecommunications, but they are so difficult that we only look for good solutions (i.e. approximations to the best solutions).

Research Interests

• Complexity theory
• Approximation theory
• Graph theory
• Optimization

Past/Current research

I have worked on bandwidth assignment in wireless networks, and particularly interested in the Gathering Problem in which there is a set of radio devices, each one of them with an unique independent piece of information that has to be delivered to a specific node of the network. Since the communication between the nodes is performed by radio transmissions, there are interference constraints that must be satisfied.

The motivation of my research comes from problems related to taking internet to small (isolated) villages.

I've written an engineering thesis under the title Mathematical models for mining engineering. I've also written an INRIA Research Report (I.R.R.) on this topic: RR-5044 : Robust models for simultaneous open pit and underground mines

About my thesis research, the I.R.R. RR-5432 : On the Complexity of Bandwidth Allocation in Radio Networks with Steady Traffic Demands is available. The paper is accepted for a spacial issue of the Journal of Theoretical Computer Science.

A second paper: Hardness and approximation of gathering in static radio networks, FAWN'06, Pisa, Italy (preprint here). The full version of the paper has appeared in the Journal of Parallel Processing Letters (PPL), Vol 2, June 2006. Research reports are available at INRIA, I3S/CNRS and LaBRI.

The third paper on the topic: Nearly optimal strategies for gathering in specific static radio networks has appeared in Algotel'06. Here is a preprint with the results of the papers (no proofs).

No so related with my thesis, I've also worked with my close friend Benjamín Bustos in indexing frequently used combinations of feature vectors, which is a problem that comes from multimedia database applications.

Some presentations

I've done a some of presentatios during my PhD. Some of them contain nice pictures about the problems I work in.

• The very first presentation, in ECOTEL (Dec. 2004), in pdf. It contains the main ideas (partial results, tho).
• Two presentations for CONICyT comittee (both in pdf) 2004 and 2005. Those are good for more general explanation of the problem and techniques.
• A more hardness-point-of-view presentation I did in JGA05, again in pdf.

Some links

• An (excellent) compendium of NP optimization problems by Viggo Kann.
• The bibliography of project MASCOTTE.
• Conferences to come.

Contact

You can write me to .

Last modified: July 24, 2006