Weighted-Sequence Problem

Problem Description

In the weighted-sequence problem we are given a set of leaves (nodes) and an integer m — maximum cost. Each leaf is a pair (weight, cardinality) where weight and cardinality are integers. Every sequence (permutation) of leaves is such that all leaves but the first are assigned a color. A colored sequence is associated with the cost. The task is to find a colored sequence with the cost at most m.

For a set S of leaves and an integer m, we denote the corresponding weighted- sequence problem by [S, m]. We say that an integer m is optimal with respect to a set S of leaves if m is the least integer u such that the weighted-sequence problem [S, u] has a solution.

Let M be a sequence of n leaves l_0, ..., l_{n−1}. For each leaf l_i , 0 ≤ i ≤ n − 1, by w(l_i) and c(l_i) we denote its weight and cardinality, respectively. We color each leaf l_i , 1 ≤ i ≤ n − 1, green, red, or blue; the leaf l_0 is not colored. We define the costs of leaves as follows. For the leaf l_0, we set cost(l_0) = w(l_0).

For every colored leaf l_i , 1 ≤ i ≤ n − 1, we set

• w(l_i) + c(l_i) if l_i is green

• cost(l_i) = cost(l_{i−1}) + w(l_i) if l_i is red
  • cost(l_{i−1}) + c(l_i) if l_i is blue

The cost of the sequence M is the sum of the costs of its colored leaves: cost(M ) = cost(l_1) + ... + cost(l_{n−1}).

Predicates

• Input: leafWeightCardinality/3, num/1, max_total_weight/1, innerNode/1

• Output: solution/2

Input format

An input consists of the following parts:

• n leaves are given with corresponding weight and cardinality (there are 1..n leaves):

  • leafWeightCardinality(leaf1,w1,c1). ... leafWeightCardinality(leafn,wn,cn). where w1..wn, c1..cn are integers.

• The number of leaves in the tree is given by num(n).

• Integer mv is given by max_total_weight(mv).

• n-1 inner nodes are given: innerNode(1). ... innerNode(n-1).

Output format

A solution is represented by means of a constant "exists" if there is a tree T and a specification of T in the following format

• posColor(1,color) ... posColor(n,color)

  leafPos(1,pos) ... leafPos(n,pos) where pos is a location in the sequence

Example(s)

Problem Peculiarities

Type: Search Competition: Both

Notes and Updates

Author(s)

• Authors: Marcello Balduccini, Yuliya Lierlier, Shaden Smith
  • Affiliation: Kodak Research Labs and University of Kentucky