Что творится с дейта сайнсом?

[Мальчик-Одуванчик]

Ближайший кластер - в Окланде. До него примерно 20 миль. И посылки идут именно туда в большинстве случаев. Но только медиа-мейл исходя из соображений оптимизации тупо прется за сотни миль в Лос-Анжелес, а потом обратно. Без математики тут явно не обошлось.
Со стороны выглядит как феерическая тупость: сначала на месте отсортировать медиа-почту отдельно от остального потока, а потом запердолить получившееся черти-куда.

Хорошее с точки зрения бизнеса решение не всегда интуитивно понятно человеку со стороны. Это не значит, что решение плохое, это значит что человек не видит картину целиком.

Но чаще всего - обычная тупость эффективных менеджеров. Разумеется с привлечением математики. (чтобы даже самим непонятно было)

[fruit6]

Дело в том, что media mail был введен как более дешевый способ доставки. Плюс USPS медленно реагирует на всё, например открыть или переоборудовать сортировочный центр если объемы превышают ожидаемое занимает месяц+, даже в горячий сезон типа декабрь (бугага). Я даже не уверен, что media попадает в обычные категории которыми оперирует почта: flats and packages. Это что-то третье разрядное. Хотите сервис - шлите посылку

[fruit6]

На почте кстати нет никаких эффективных менеджеров.

[Larsonsager]

Полиномиальное решение, судя по названию, это FPTAS.

Короче говоря, вы заявляете, что знаете FPTAS, который решает задачу о Гамильтоновом пути на неметрическом графе!?

Отлично, теперь вы узнали, что такое FPTAS. А теперь перечитайте тред и попытайтесь найти место, где я якобы заявляю, будто задача о гамильтоновом пути на неметрическом графе решается каким-то FPTAS. Я изначально писал про задачу о рюкзаке. Вы сперва оскорбительно проехались по моему комментарию, решив, что раз вы что-то смутно помните о NP-полных задачах - значит, мои слова о полиномиальном решении сравнимы с "делом Петрика". А когда поняли, что облажались, решили приписать мне слова о полиномиальном нахождении гамильтонова пути.

[tessob]

А теперь перечитайте тред и попытайтесь найти место, где я якобы заявляю, будто задача о гамильтоновом пути на неметрическом графе решается каким-то FPTAS.

Мы говорили о задаче с контейнерами. Сначала вы заявили, что способны установить отличие глобального минимума от локального для дискретной функции. Я попросил поделиться секретом с общественностью.

Вы заявили, что достаточно будет провести n экспериментов. А чё бы и нет!? Представьте что вы исследуете Y=X^Х которая задана только для X, являющихся натуральными числами на интервале 0:10^30000. Ну разве не «П####Ц»!?

Следом вы заявляете, что именно так, за полином, и решают задачу о рюкзаке, и за этим даже стоит математика. Разумно? Разумно! Рандом — верный путь к полиному! Ну чем не заявка на премию Петрика!? Разумеется, я не мог, просто из любопытства, не попросить привести этот волшебный алгоритм.

Тот алгоритм, что вы привели — обычное динамическое программирование, релаксированное пропорциональным уменьшением капасити и весов. Просто, матрица для динамики с рюкзаком строится как [ число предметов , капасити рюкзака ]. Ваш FPTAS в данном случае просто уменьшет размер матрицы, чтоб обходить не MxN, а MxN/K. Если вы посмотрите сорцы, то после деления всего и вся, идет вызов динамики. Однако, удивительным образом, никакой рандомизации в алгоритме не оказалось.

В итоге, исходя из вашей аргументации, следует, что: задача о контейнерах решается так же как и рюкзак, а рюкзак решается fptas. Следовательно, допустив транзитивность, я и решился уточнить, есть ли у вас fptas для Гамильтонова пути. Вдруг есть.

UPD:
И кстати, ваш FPTAS для рюкзака не находит решение за полином. Он работает за полином. А найдет он решение или нет, будет зависеть от входных данных. Сможете сказать почему?

[Larsonsager]

> В итоге, исходя из вашей аргументации, следует, что: задача о контейнерах решается так же как и рюкзак

Это ваши домыслы. Я не говорил, что задача о контейнерах решается так же, как и рюкзак. Было бы абсурдным говорить это, пока задача о контейнерах вообще не сформулирована. Мои слова про локальный минимум были ответом на вашу фразу:

> Это задача дискретной математики в пространстве натуральных чисел. В математике
> вообще пока нет ни одного непереборного алгоритма, который бы находил min/max решение
> подобных задач за менее чем n! шагов.

- я сказал, что так как на практике нас может устроить локальный минимум вместо глобального, если он не сильно хуже, то для ряда задач дискретной математики в пространстве натуральных чисел [не решаемых строго за приемлемое время] есть принципиально более быстрые приблизительные решения. И привёл два примера: (1) рандомизированные алгоритмы, решающие, например, задачу рюкзака за полиномиальное время и (2) релаксацию условия целочисленности [например, LP-релаксацию] с последующими эвристиками возврата к целочисленности.

> Тот алгоритм, что вы привели — обычное динамическое программирование

FPTASность не имеет никакого отношения к динамичности. Если конкретная реализация использует динамику - ну, хорошо, почему бы и нет. И нет, это не та же динамика, что при строгом решении. Суть FPTAS в том, что, хотя для глобального оптимума требуется, по сути, полный перебор всех вариантов или около того, можно найти оптимум, отстоящий от глобального на приемлемую величину, не перебирающий все варианты.

Возвращаясь к вашим словам, будто я "заявил, что способен установить отличие глобального минимума от локального": я этого не заявлял, а заявлял я, цитирую: "вместо глобального минимума находится тот из локальных, что мало отличается от глобального". Чтобы найти локальный, мало отличающийся от глобального, глобальный отличать от локального не нужно. Достаточно знать, что он не может быть гораздо лучше найденного (гарантированно не может или вероятностно вряд ли является), над чем работают математики, результатами которых могут пользоваться алгоритмисты. Например, для той же LP-релаксации задач целочисленного программирования может оказаться возможным оценить отличие найденного решения от оптимального, найдя, скажем, зазор двойственности (duality gap) с соответствующей выпуклой задачей.

[Lisa]

Я восхищаюсь вашим терпением, коллега.

[tessob]

Это ваши домыслы. Я не говорил, что задача о контейнерах решается так же, как и рюкзак. Было бы абсурдным говорить это, пока задача о контейнерах вообще не сформулирована.

Это как бы не совсем так, ну, ...или совсем не так...

Сначала был мой пост:

Lisa, вам формально нужно найти оптимальный гамильтонов путь в полносвязном графе в 8’000 вершин. Число возможных гамильтоновых путей у такого графа будет примерно 10 ^ 30’000.

Следом ваш:

Никому не нужно решать подобные задачи строго. Из того, что задача о рюкзаке или коммивояжера не решаются строго за приемлемое время, не следует, что они вообще не решаются за приемлемое время. Просто вместо глобального минимума находится тот из локальных, что мало отличается от глобального.

Смотрите внимательно на даты и время. Все ходы записаны.
Рюкзак к обсуждению, в качестве аргумента, приплели вы, а не я.

FPTASность не имеет никакого отношения к динамичности. Если конкретная реализация использует динамику - ну, хорошо, почему бы и нет.

Понятие "FPTASность" мы оставим за скобками.
Правильно ли я понимаю, что вы знаете другой FTPAS для рюкзака, который не использует динамическое программирование?

И нет, это не та же динамика, что при строгом решении. Суть FPTAS в том, что, хотя для глобального оптимума требуется, по сути, полный перебор всех вариантов или около того, можно найти оптимум, отстоящий от глобального на приемлемую величину, не перебирающий все варианты.

Динамика ровно та самая, которая единственная. Если вы откроете книжку Вазирани, которой тыкали мне в нос, то на страничке 70 будет описан ровно тот самый алгоритм, который имплементирован студентом бауманки. Динамика просто итерирует по предметам и капасити и для каждого нового значения матрицы решений выполняет довольно жадную проверку на максимум. Где там хоть намек на тот оптимум, про который вы тут пишете? В каком месте алгоритм ищет "оптимум, отстоящий от глобального на приемлемую величину"? Где именно задана эта приемлемая величина, в какой строке имплементации!?

И что вы, в случае динамики, понимаете под "при строгом решении"? В предыдущем сообщении я вас попытался спросить знаете ли вы условия, когда динамика не сможет придти в глобальный минимум. Вы не сочли нужным отвечать. Не проблема. Однако, вместо этого, вы решили продемонстрировать свое незнание этого.

Возвращаясь к вашим словам, будто я "заявил, что способен установить отличие глобального минимума от локального": я этого не заявлял, а заявлял я, цитирую: "вместо глобального минимума находится тот из локальных, что мало отличается от глобального".

Как вы определяете меру отличия!?!?!?

Larsonsager, если хотите, то я вам сведу задачу о контейнерах к канонической задаче о Гамильтоновом пути? Сможете продемонстрировать:

(1) рандомизированные алгоритмы, решающие, например, задачу рюкзака за полиномиальное время и (2) релаксацию условия целочисленности [например, LP-релаксацию] с последующими эвристиками возврата к целочисленности.

Словами не передать как я хочу увидеть "рандомизированные алгоритмы, решающие, например, задачу рюкзака за полиномиальное время". Вы бы хоть пример такого алгоритма привели. Это же прорыв в математике будет, не иначе.
Что касается LP-релаксации, то я бы с удовольствием посмотрел:
1) Как вы будете приводить к линейной канонической форме задачу о гамильтоновом пути. В первую очередь мне будет интересно глянуть как вы будете решать проблему коммутативности иксов.
2) Как вы будете эвристиками возвращаться к целочисленности в задаче о рюкзаке, где у вас сложность 2^n. У вас для всех иксов будет задано неравенство 0 <= X <= 1. Зато линейные уравнения сформулировать просто.

Я восхищаюсь вашим терпением, коллега.

Lisa, не скромничайте, пролейте уже наконец свет на современные методы исследования операций. Просто, пока ничего кроме ваших голословных утверждений о ваших выдающихся успехах, в этой теме с вашей стороны не прозвучало. У вас есть шанс это исправить.

[Lisa]

Lisa, не скромничайте, пролейте уже наконец свет на современные методы исследования операций. Просто, пока ничего кроме ваших голословных утверждений о ваших выдающихся успехах, в этой теме с вашей стороны не прозвучало. У вас есть шанс это исправить.

Larsonsager вам там уже выше все очень подробно расписал.

[Lisa]

К нам тут недавно тоже приходили third party провайдеры, впаривали свою простенькую плохонькую эвристику. Потому что задача ну такая сложная, такая сложная, ничего лучше ну никак нельзя. Нарвались, конечно.

[tessob]

К нам тут недавно тоже приходили third party провайдеры, впаривали свою простенькую плохонькую эвристику. Потому что задача ну такая сложная, такая сложная, ничего лучше ну никак нельзя. Нарвались, конечно.

Lisa, к вам third party провайдеры в снах являться стали?

Вы уж простите, но я не верю ни единому вашему слову. Вы, в этой теме, привели ровно 0 аргументов по-существу и целую кучу громких заявлений.

[Lisa]

К нам тут недавно тоже приходили third party провайдеры, впаривали свою простенькую плохонькую эвристику. Потому что задача ну такая сложная, такая сложная, ничего лучше ну никак нельзя. Нарвались, конечно.

Lisa, к вам third party провайдеры в снах являться стали?

Вы уж простите, но я не верю ни единому вашему слову. Вы, в этой теме, привели ровно 0 аргументов по-существу и целую кучу громких заявлений.

Мне совершенно все равно чему вы верите или не верите. Это ваши проблемы. У меня только больше выбор работ будет.

[alex_127]

Мне говорили что потолок низковатый. Не скажите - так ли это. Есть ли куча народа с 350к+ Или мы скатываемся к единицам...