Как Вы оцениваете эффективность алгоритма, если пространство задач является underspecified?

Было сообщение на здесь недавно, которое поставило следующий вопрос:

У Вас есть двухмерная плоскость (X, Y) координаты. Набор случайных точек выбран. Необходимо выбрать самый большой набор выбранных точек, таких, что никакие две точки не совместно используют X координат, и никакие две точки не совместно используют координату Y.

Это - вся информация, которая была предоставлена.

Было два представленные возможных решения.

Одно предложенное использование максимального алгоритма потока, такого, что каждая выбранная точка отображается на путь, связывающийся (источник → X → Y → приемник). Это выполняет в O ^(V3) время, где V количество выбранных вершин.

Другой (шахта) предложил использовать венгерский алгоритм. Создайте n×n матрицу 1 с, затем установите каждый выбранный (x, y) координата к 0. Венгерский алгоритм даст Вам самую низкую цену для этой матрицы, и ответ является количеством координат, выбранных который равный 0. Это выполняет в O ⁽ⁿ³⁾ время, где n является большим из количества строк или числа столбцов.

Мое обоснование состоит в том, что для подавляющего большинства случаев венгерский алгоритм будет быстрее; V равно n в случае, где существует одна выбранная точка для каждой строки или столбца, и существенно больше для любого случая, где существуют больше, чем это: данный 50×50 матрица с половиной выбранных координат, V 1,250, и n равняется 50.

Контрдовод - то, что существуют некоторые случаи, как ^109×109 матрица только с двумя выбранными точками, где V 2, и n 1,000,000,000. Для этого случая венгерскому алгоритму требуется смехотворно долгое время для выполнения, в то время как максимальный алгоритм потока ослепляет быстро.

Вот вопрос: Учитывая, что проблема не предоставляет информации относительно размера матрицы или вероятности, что данная точка выбрана (таким образом, Вы не можете знать наверняка), как Вы решаете, какой алгоритм, в целом, является лучшим выбором для проблемы?