теория алгоритмов2 math.

[drifting_along]

Пожалуйста, помогите перевести слово flipped в следующем контексте: While the random inputs considered in these analyses are not as special as the random inputs obtained from spherically symmetric distributions, the model of randomly flipped inequalities provokes
some similar objections.
И, если кто-нибудь знает, напишите, пожалуйста, как на русском называется задача bandwidth problem. Она формулируется следующим образом: The bandwidth problem is the problem of enumerating the vertices of a given graph G such that the maximum difference between the numbers of adjacent vertices is minimal.

[WoodyWoo]

По первому вопросу трудно сказать, контекст нужен еще шире. Что за модель такая? Без контекста "model of randomly flipped inequalities" выглядит как "модель со случайным выбором знаков неравенства".

Bandwidth problem - это, судя по всему, задача о максимальном потоке.

[drifting_along]

Спасибо Вам огромное, WoodyWoo. Вы меня уже не в первый раз выручаете. Насчет flipped мне даже в институте математики ничего вразумительного не сказали, так что особо не парьтесь. Контекст здесь не бог весть какой. Просто во введении авторы упоминают исследования, на которых базируется их работа, а потом уже другой раздел идет. Вот целый абзац:
Another model of random linear programs was studied in a line of research initiated
independently by Haimovich [Hai83] and Adler [Adl83]. Their works considered the maximum
over matrices, A, of the expected time taken by parametric simplex methods to solve
linear programs over these matrices in which the directions of the inequalities are chosen at
random. As this framework considers the maximum of an average, it may be viewed as a
precursor to smoothed analysis—the distinction being that the random choice of inequalities
cannot be viewed as a perturbation, as different choices yield radically different linear
programs. Haimovich and Adler both proved that parametric simplex methods would take
an expected linear number of steps to go from the vertex minimizing the objective function
to the vertex maximizing the objective function, even conditioned on the program being
feasible. While their theorems confirmed the intuitions of many practitioners, they were
geometric rather than algorithmiс as it was not clear how an algorithm would locate either
vertex. Building on these analyses, Todd [Tod86], Adler and Megiddo [AM85], and Adler,
Karp and Shamir [AKS87] analyzed parametric algorithms for linear programming under
this model and proved quadratic bounds on their expected running time. While the random
inputs considered in these analyses are not as special as the random inputs obtained from
spherically symmetric distributions, the model of randomly flipped inequalities provokes
some similar objections.