## G. Cormode.
Topic dependencies for electronic books.
(unpublished manuscript), 1999.

Electronics books consist of a number of topics, and information about dependencies between
topics. We examine some theoretical problems related to handling these topic dependencies. In
particular we consider the case where these topic dependencies are acyclic, and nondecomposable
(that is, if topic *a* and *b* together require *c*, it is not necessarily the case that *a* or *b* alone require
*c*). We formalise the semantics of this system, and give an axiomatisation which we show is
sound and complete. We then show that we can easily compute the closure of a set of all topics
in this model, which is the set of topics which are required by that set. This closure is computed
in an identical manner to that for other formalisations of topic dependencies, showing that for
this purpose no distinction need be drawn.
We then consider a different kind of closure, where given a set of desired topics, we must
find a subset such that the total running time of all topics in its closure is less than a given time
bound. We show that this problem is NP-complete. We analyse some proposed heuristics to
approximate the solution of this problem and demonstrate that inputs can be engineered which
elicit very poor performance from these heuristics, showing that no factor of approximation can
be guaranteed for them. Finally, we transform the problem into a problem over a bipartite
graph, which in turn can be formulated as a problem in mathematical integer programming.
Hardness results for this problem give us confidence that a guaranteed approximation is unlikely
to exist.

[ bib |
.pdf ]
Back

*This file was generated by
bibtex2html 1.92.*