Loading...
Please wait, while we are loading the content...
Similar Documents
M.: Optimal website design with the constrained subtree selection problem (2004)
| Content Provider | CiteSeerX |
|---|---|
| Author | Heeringa, Brent Adler, Micah |
| Abstract | Abstract. We introduce the Constrained Subtree Selection (CSS) problem as a model for the optimal design of websites. Given a hierarchy of topics represented as a DAG G and a probability distribution over the topics, we select a subtree of the transitive closure of G which minimizes the expected path cost. We define path cost as the sum of the page costs along a path from the root to a leaf. Page cost, γ, is a function of the number of links on a page. We give a sufficient condition for γ which makes CSS NP-Complete. This result holds even for the uniform probability distribution. We give a polynomial time algorithm for instances of CSS where G does not constrain the choice of subtrees and γ favors pages with at most k links. We show that CSS remains NP-Hard for constant degree DAGs, but also provide an O(log(k)γ(d + 1)) approximation for any G with maximum degree d, provided that γ favors pages with at most k links. We also give a complete characterization of the optimal trees for two special cases: (1) linear degree cost in unconstrained graphs |
| File Format | |
| Language | English |
| Publisher Date | 2004-01-01 |
| Publisher Institution | In 31st Intern. Colloquium on Automata, Languages, and Programming (ICALP |
| Access Restriction | Open |
| Subject Keyword | Optimal Website Design Constrained Subtree Selection Problem Favor Page Degree Cost Complete Characterization Polynomial Time Algorithm Page Cost Uniform Probability Distribution Transitive Closure Constrained Subtree Selection Probability Distribution Sufficient Condition Cs Np-complete Path Cost Maximum Degree Expected Path Cost Special Case Unconstrained Graph Optimal Tree Optimal Design Constant Degree Dag |
| Content Type | Text |
| Resource Type | Technical Report |
