-
Given n_1 jobs of length p_1, n_2 jobs of length p_2, n_3 jobs of length
p_3, given m machines, and a deadline D, does there exist a feasible
schedule? (i.e. a schedule in which each job is scheduled nonpreemptively at
some machine and completed no later than time D).
Does there exist a polynomial-time algorithm to answer this question or is
the problem NP-complete?
- Wavelength conversion in optical networks
Regarding the problem of computing small placements of converters in
optical networks with shortest-path routings, we still do not have good
approximation algorithms. Our results indicate that it is unlikely or at
least highly non-trivial to obtain a constant factor approximation
algorithm. Therefore, we believe that a promising direction for future
research is to investigate whether there is an approximation algorithm
achieving logarithmic approximation ratio.
- Wavelength conversion in optical networks with dynamic routings
Our work on optical networks with dynamic routings points to several
interesting directions for future research. In particular, it would be
interesting to develop algorithms for testing whether a placement of
wavelength converters results in optimal capacity usage in networks with
dynamic arbitrary or shortest-path routings. Also, the problem of
computing small placements of converters in these networks is worth studying.
- In the context of OVSF code assignment, we have been considering various
online strategies. The only known strategy with constant competitive
ratio needs an additional layer of codes. It is still open to find such a
strategy exists, that guarantees a constant competitive ratio, without
additional resources, and independent of the height of the code tree.
- Broadcast Scheduling
- Find a non-trivial approximation algorithm which does not use resource
augmentation, so far from below only NP-hardness is known.
- Experimental analysis: how do algorithms perform on real-world data
(e.g. traces of Web-Servers).
- Flows over Time
- Close a gap: for the quickest multicommodity flow problem in the setting
with constant transit times and where intermediate storage of flow is
prohibited. From above a $2$-approximation algorithm has been given and
from below it was shown that no FPTAS exists, unless $\P = \NP$. This gap
seems particularly interesting, since the $2$-approximation is based on
computing temporally repeated flows, which have a relatively simple
structure; but no better ratio can be achieved with this technique.
- Consider other models of flow-dependent transit times: devise a
mathematical model that both captures real-world behavior as accurately
as possible and can still be solved efficiently, even on large networks.
- Customer-Provider Relationships in the Internet
- Integrate other (frequent) commercial relationships into the
setting.
- Concerning connectivity issues: study special graph classes, search for
fixed-parameter tractable algorithms, consider the multi-cuts and
multiway-cuts problems.
|