0
$\begingroup$

Problem Statement:

Given: an ordered list of N items, which we can refer to by index: [0, N).

Goal: Write an algorithm to incrementally generate indexes that are as far away from all previously returned indexes as possible. In the base case where no indexes have been returned so far, we can start with either the first or the last index. Choosing the first or last index is symmetric, so by convention we will always start with the last index: N - 1.

Examples:

For example, if we had 4 items, in the first round by convention we yield 3. Then we have to return the farthest index from 3, so we yield 0. Then in the next round both 1 or 2 have the same minimum distance to a previously yielded index, so we can chose either. Let's choose 2. Then in the final round there is only one index left, so we have to choose 1. So an optimal sequence for 4 items is: [3, 0, 2, 1].

For another example, if there are 10 items, an optimal sequence is: [9, 0, 5, 2, 7, 1, 6, 3, 8, 4]

Implementation:

Working with @LeeSE we've written a Python implementation and claim it solves the problem:

def farthest_from_previous(start: int, stop: int):
    """
    Given a ordered list of items, incrementally yield indexes such that each
    new index maximizes the distance to all other previously chosen indexes.

    Args:
        start (int): The inclusive starting index (typically 0)
        stop (int): The exclusive maximum index (typically ``len(items)``)

    Yields:
        int: the next chosen index in the series

    Example:
        >>> total = 10
        >>> start, stop = 0, 10
        >>> gen = farthest_from_previous(start, stop)
        >>> result = list(gen)
        >>> assert set(result) == set(range(start, stop))
        >>> print(result)
        [9, 0, 5, 2, 7, 1, 6, 3, 8, 4]
    """
    import itertools as it

    def from_starts(start: int, stop: int):
        if start < stop:
            low_mid: int = (start + stop) // 2
            high_mid: int = (start + stop + 1) // 2

            left_gen = from_starts(start, low_mid)
            right_gen = from_starts(high_mid, stop)

            pairgen = it.zip_longest(left_gen, right_gen)
            flatgen = it.chain.from_iterable(pairgen)
            filtgen = filter(lambda x: x is not None, flatgen)
            yield from filtgen
            if low_mid < high_mid:
                yield low_mid
    if start < stop:
        yield stop - 1
        yield from from_starts(start, stop - 1)

Motivation:

I have a directory of ordered images images that were generated to visualize neural network training iterations. I create one of these directories every time I train a network.

These visualizations can start to take up too much disk space, and removing some percent of them would free up a lot of space, but still leave some of the visualizations in case I wanted to go back and inspect an old run. So the question is: which of these images do I keep? By incrementally generating "furthest from previous" indexes and checking if the total size exceeds some threshold, I can stop, keep all files corresponding to generated indexes, and remove the rest.

Question for CS Stack Exchange:

My attempts to determine if this problem or variants of it have been formally studied have turned up empty so far. My question is: does this problem have a name, or is there an instance of it or something similar that exists in the literature?

It's clearly some greedy knapsack variant. But the value of each item depends on the other items that are selected.

It is similar to the set union knapsack problem (SUKP) because the optimality of a decision depends on previous decisions, but in SKUP that is codified by the dependent weights, whereas in this problem the weights are constant, but the value of the next item changes based on the previous item.

It looks like in 2023 there was a paper https://link.springer.com/article/10.1007/s10479-023-05265-x describing "Position-Dependent Knapsack" where the "profit of an item depends on the position of the item in the sequence of items packed in the knapsack", that looks promising as a framework for studying this greedy variant. It also looks like there is another similar 2023 paper from a different team: https://www.sciencedirect.com/science/article/pii/S1877050923010335

But thinking about it, perhaps position isn't enough to codify the concept of certain selections of items being worth more based on higher order relationships between items in the selection. It looks like this 2017 paper: "An Integer Linear Programming Model for Binary Knapsack Problem with Dependent Item Values" https://link.springer.com/chapter/10.1007/978-3-319-63004-5_12 may be an exact fit to the non-greedy generalization of this problem.

Still, I'm curious if others can point me at references to help me better understand the scope of existing work around this problem.

$\endgroup$
2
  • $\begingroup$ Do you have a running time requirement for the algorithm, or is any polynomial-time algorithm OK? $\endgroup$
    – D.W.
    Commented May 5 at 20:05
  • $\begingroup$ I'm not looking for a specific algorithm (although I am interested if you have one for the non-greedy variant). I'm more interested in existing related work. My research is in machine learning, so I'm not as up to date in theoretical CS papers as I would like to be. $\endgroup$
    – Erotemic
    Commented May 5 at 20:56

1 Answer 1

1
$\begingroup$

This is an instance of farthest-point traversal in 1D.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.