Я не спала всю ночь, дожидалась приземления самолета. Подумала: нужно себя как-то развлечь и зашла на хабр. Все подробности об отправке лекарств я сообщила. Если увидят, что отправляете лекарство - могут потребовать рецепт, согласно инструкции. Спасибо за приятное общение. Извините, если чем-то вас разочаровала.
Моя семья этим занималась. Вам же советую не слушать чужие рассказы, а воспользоваться гуглом "сдек отправка лекарств". Тогда не будет неприятной неожиданностью, что в каких-то пвз выполняют должностные инструкции.
Интересно, не знала, что обычной почтой и без рецепта принимают. Сдэк только с рецептом. Когда первый раз на это попали, аж однодневной коммерческой почтой в Москву рецепт отправляли, потом выяснилось, что достаточно фото. К слову, часто пользуюсь сдэком, никаких нареканий никогда не было.
При отправке лекарств там особый порядок, был, во всяком случае.
Добрый день, чисто ради дальнейшей информации. До недавних пор рецептурные препараты нельзя было по интернету в другой город заказывать, нужно было, чтобы кто-то с рецептом (или хотя бы копией рецепта) сам пришел в аптеку и затем вложил бумажную копию рецепта в Сдэковскую посылку. Что-то изменилось? Или у вас не рецептурный был препарат?
Языки, которыми пользовалась (турбопаскаль, паскаль + дельфи, пролог) изучала в стародавнее время с помощью бумажных учебников. Сейчас учу питон с помощью гугла, степика и статей на хабре. По-моему, на любой вопрос, который у меня возникает, есть уже статья на хабре. За что, конечно, здешним авторам отдельное спасибо.
Дополню предыдущего оратора относительно степика. Кроме поколения пайтон, очень понравился курс Артема Егорова Инди питон (бесплатный). Этот курс хорошо дополняет продвинутый курс Поколения Пайтон, у Артема замечательные видео. Я их проходила одновременно. Сейчас прохожу егоровский ООП (2 т.р.), все понятно, хорошие тренажеры кода.
Видимо, мы о разных задачах говорим. В реальных задачах оперативного планирования производства есть понятие допустимого решения. Обычно там многокритериальные задачи, большая размерность и от программы ждут, что нажал на кнопку и вышел план, допустимый в каком-то смысле.
Например, отгрузка готовой продукции со склада. Стоит под погрузкой состав, 10 вагонов, за простой - огромный штраф. Как только его отгрузят, подъедет следующий состав. И при этом еще параллельно на складе идет размещение готовой продукции, теми же кранами. И там тоже нужен план. Заказы разбросаны по складу. В условиях договора прописано: заказ отгружается с точностью до 5 тонн. Никому не нужен точный набор или лучшее приближение - как только сгенерировано допустимое решение - формируется план. И тоже самое с госзакупками, правда, здесь задача однокритериальная, нужно не оптимальное решение, а первое решение с допустимым отклонением.
Если мы сейчас обсуждаем мои скромные проекты - спасибо за советы, возможно, когда-нибудь это пригодится. Пока у меня всё работает, в точном соответствии с ТЗ.
Средняя госзакупочная сумма - 10 миллионов рублей. Переводим в копейки - миллиард. Табличка с миллиардом столбиков. Предположим, что точное решение существует. Предположим, что бухгалтер его когда-нибудь дождется. А на самом деле его устроило бы любое решение с отклонением не более, чем 100 руб.
По-моему, вы сами понимаете, что это аппроксимационный алгоритм, потому что пишите про абсолютную погрешность алгоритма.
Я подумаю, понимаю я или еще нет))
Это приближенный алгоритм, у которого абсолютная погрешность фиксирована и не зависит от количества слагаемых и величины набираемой суммы, соответственно, асимптотическая погрешность равна 1. По-моему, для NP-hard лучше не бывает.
Если всё-таки превратить эту задачу в рюкзак. Тогда она будет звучать так. Дано мн-во A предметов, у к-х нецелый вес=стоимость, и дано нецелое число B. Вопрос. Найти рюкзак с суммарным весом <= B и суммарной стоимостью >= B. ДП эту задачу решать нельзя. Для ДП нужна целочисленность хотя бы по одному параметру.
Хорошо, для ДП есть т.н. метод масштабирования. Если попытаться применить его к этой задаче. Вначале придется умножить на 100 (рубли-копейки). Затем всё нужно уменьшить в scale раз, где scale - к-т масштабирования, и отбросить дробную часть. Величина погрешности n*scale, где n - число слагаемых. Для этой задачи scale = 10000 и n = несколько сотен.
Обратите внимание, я не говорю, что ваш алгоритм плох: точные и быстрые аппроксимации - это очень обширная тема исследований и такой алгоритм очень полезен на практике.
Но все же это другой класс алгоритмов. В статье тут рассматривается точный алгоритм.
Спасибо вам на добром слове! Что он плох, мне уже сказал ТС, для к-го я два дня писала статью))
Да, это другой класс алгоритмов, обычная бухгалтерская программа для оптимизационной постановки задачи о наборе суммы. Наверно, было бы странно, если бы бухгалтер запустил программу, она бы прострекотала и сообщила, что решения нет. За сим откланиваюсь. Рюкзак так рюкзак.
Мой модельный пример. Нужно набрать 100; рабочий массив A = [11(10), 8 (20), 3, 2(10)], в круглых скобках указана кратность слагаемого. Результат работы алгоритма - [11(8), 8, 2(2)], набираем ровно 100.
Где в этой задаче вы увидели рюкзак? Не могу понять ход ваших мыслей. Это первое.
Теперь второе. Умный любит учиться, как Антон Павлович Чехов однажды заметил. Покажите, как набрать нецелочисленную сумму порядка 10^7 с помощью нескольких сотен нецелочисленных слагаемых, хоть рюкзаком, хоть ДП, хоть ЦЛП, хоть чем.
У рюкзака каждый элемент имеет вес и стоимость, здесь - только стоимость (просто я называю ее весом, так короче). Если взять целые веса и положить D=0, то получим задачу о наборе заданной суммы. Специально (для вас) взяла модельный целочисленный пример с D=0. Вы до него дочитали?
А вообще в этом нет ничего удивительного, NP-полные задачи друг к другу полиномиально сводятся. Сейчас пишу с телефона, неудобно, доберусь до десктопа, докажу полиномиальную сводимость для Рюкзака и Суммы размеров.
И спорить в вами не буду, вы правы. Для сверхбольшой размерности делают особые алгоритмы. Пусть будет не сверхбольшая, а большая производственная размерность.
Нет, там не рюкзак, там чистый набор заданной суммы заданными слагаемыми по недостатку (недобрать можно, перебрать нельзя). Программы у меня нет, т.к. писали под какую-то конкретную бухгалтерскую программу. Прям отдельную статью про это писать не хочется (тем более, она опубликована в "Информационных технологиях"), просто выложу сюда описание первой, приближенной части алгоритма. И на примере покажу, как он работает.
Делала два раза подобную задачу в сверхбольшой размерности: при отгрузке листопроката (но там кроме набора заданного веса было ограничение на количество перекладываний в штабелях и дополнительно нужно было освобождать рабочее пространство склада). А вот второй раз при госзакупках нужно было выбрать выделенную на подразделение сумму с помощью списка: товары, их стоимость, требуемое количество. Суммы были огромные, но программа набирала с точностью нескольких рублей (программу писала работающая в бухгалтерии дипломница, алгоритм описан в статье, если кому интересно, дам ссылку). Идея гибридного алгоритма. Основная часть суммы набирается довольно хитрым не совсем жадным алгоритмом, т.к. производятся некоторые возвраты. Добор небольшой суммы не более чем 20 слагаемыми производится точным алгоритмом. Работает быстро и довольно точно, верхняя оценка погрешности величина последнего добавленного слагаемого, числа не целые (рубли, копейки).
Я закончила мехмат в 1982 г. Выпустили половину от набора, особо не отчисляли, у нас был очень хороший начальник курса, Петр Иванович Пасиченко, люди забирали документы и переводились в технические вузы или провинциальные университеты. Из получивших диплом немногие стали "профессиональными" математиками, большая часть стала как раз программистами. И в "ящиках", и в различных НИИ. Даже как-то смешно читать о том, что выпускник мехмата не может стать программистом. Моя близкая подруга, и одноклассница в школе, и одногруппница в МГУ, распределилась в Новосибирский академгородок, стала системным программистом (Эльбрус), потом много лет в Израиле в фирме работала, потом, как говорила Анна Ахматова, "стара собака стала", вернулись с мужем в Новосибирск, до сих делают проекты как фрилансеры.
Что касается детей-вундеркиндов, которых я много повидала и как преподаватель, и как родитель (дочь у меня в 14 лет школу закончила), то на них равняться не надо, жизнь у них тяжёлая, особенно если родители сдуру отправляют их учиться не по возрасту.
Теперь история из жизни. У профессора моей кафедры (по образованию теплотехника, но ставшего программистом), был любимый аспирант, очень одаренный парень, из математической школы. Аспирант успешно защитил кандидатскую, уехал с женой в не резиновую, там не понравилось, нашел фирму в Австралии, прошел тест. Тут из фирмы просят документ об образовании, и он отправил им свой кандидатский диплом. Нет, у нас работа простая, такой квалифицированный нам не нужен. Нашел другую фирму, в Новой Зеландии, прошел тест, собеседование, прислал бакалаврский диплом нашей кафедры - уже давно живёт в Н.З.
Еще раз спасибо. В данный момент я думаю, как переписать свои программы с графами с паскаля на питон. Видимо, питон был не лучший выбор, но не хочется бросать на полпути.
Что касается вашего вопроса о постановке задачи для поиска абсолютного центра. Сейчас открыла статью, вспомнила, какую "реальную" постановку я придумала (придумала, т.к. в редакции просили дать практическое приложение для алгоритма). В качестве вектора весов используются две характеристики ребра: длина и стоимость.
Задача о платных дорогах.
Условие. Дан неор. граф, каждому ребру приписаны положительная длина и положительная стоимость. Вершины взвешены, веса неотр. (вес вершин - "важность" клиентов. Если все клиенты одинаковы, то веса единичные). Задана положительная граница стоимости B. Требуется разместить абсолютный центр (в любой точке графа) так, чтобы стоимость проезда от центра до любого клиента не превосходила B, а взвешенное расстояние до самого удалённого клиента было минимально.
Там целая серия весьма прикладных задач, во-первых разные типы обслуживающих центров (центры - минимизируем расстояние от центра до самого удалённого клиента и медианы - минимизируем сумму расстояний от всех клиентов до центра), в разных вариациях: обслуживающие центры в вершинах или посреди ребра (дуги); клиенты в вершинах или в любой точке ребра (дуги). Один обслуживающий центр размещается за полиномиальное время, далее - NP-hard. Из P нетривиальная задача только одна - размещение абсолютного центра на неор. графе. У нас по старинке её до сих пор графическим алгоритмом Хакими решают, для графа с невзвешенными вершинами.
Я сделала размещение абс. центра с ограничениями (ребру приписан вектор весов), вроде на тот момент не было таких постановок или я плохо искала, во всяком случае, опубликовали в ИТ и ВС в 20-м году. Вот мой список литературы, не знаю, как в спойлер убрать:
1. Hakimi, S.L. 1964. Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph. Operations Research 12:450–459. doi:10.1287/opre.12.3.450.
2. Kariv, O. & Hakimi, S.L. 1979. Algorithmic approach to network location problems, I: The p-Centers, SIAM J. Appl. Math. 37(3):513–537. doi:10.1137/0137040.
3. Goldman, A.J. Minimax location of a facility in a network. Transp. Sci. 6(4):407–418. doi:10.1287/trsc.6.4.407.
4. Megiddo, N. 1983. Linear-time algorithms for linear programming in R3 and related problems. SIAMJ. Comput. 12(4): 759–776. doi:10.1137/0212052.
5. Ding, W. & Qiu., K. 2017. FPTAS for generalized absolute 1-center problem in vertex-weighted graphs. Journal of Combinatorial Optimization. 34(4):1084–1095. doi: 10.1007/s10878-017-0130-4.
6. Ramos, R.M., Sicilia, J. & Ramos, M.T. 1997. The biobjective absolute center problem. TOP, 5(2): 187-199. doi: 10.1007/BF02568548.
7. Ding, W. & Qiu., K. 2015. Approximating the Restricted 1-Center in Graphs. In: Lu Z., Kim D., Wu W., Li W., Du DZ. (eds) Combinatorial Optimization and Applications. Lecture Notes in Computer Science, vol 9486: 647-659. doi: 10.1007/978-3-319-26626-8_47.
8. Minieka, E. 1981. Polynomial Time Algorithm for Finding the Absolute Center of a Network. Networks, 11: 351-355. doi:10.1002/net.3230110404
9. Minieka, E. 1978. Optimization Algorithms for Networks and Graphs. New York: Marcel Dekker. 356 p.
10. Christofides, N. 1975. Graph Theory: Algorithmic Approach. New York: Academic. 400 p.
Я не спала всю ночь, дожидалась приземления самолета. Подумала: нужно себя как-то развлечь и зашла на хабр. Все подробности об отправке лекарств я сообщила. Если увидят, что отправляете лекарство - могут потребовать рецепт, согласно инструкции. Спасибо за приятное общение. Извините, если чем-то вас разочаровала.
Моя семья этим занималась. Вам же советую не слушать чужие рассказы, а воспользоваться гуглом "сдек отправка лекарств". Тогда не будет неприятной неожиданностью, что в каких-то пвз выполняют должностные инструкции.
Я сама ничего не отправляю, этим занимается муж :)
Сын из мск присылал сдеком лекарства, я лекарства никогда не отправляла.
Интересно, не знала, что обычной почтой и без рецепта принимают. Сдэк только с рецептом. Когда первый раз на это попали, аж однодневной коммерческой почтой в Москву рецепт отправляли, потом выяснилось, что достаточно фото. К слову, часто пользуюсь сдэком, никаких нареканий никогда не было.
При отправке лекарств там особый порядок, был, во всяком случае.
Неаптека вложила рецепт в просто посылку? Или Сдэк перестал требовать рецепт при отправке лекарств?
Добрый день, чисто ради дальнейшей информации. До недавних пор рецептурные препараты нельзя было по интернету в другой город заказывать, нужно было, чтобы кто-то с рецептом (или хотя бы копией рецепта) сам пришел в аптеку и затем вложил бумажную копию рецепта в Сдэковскую посылку. Что-то изменилось? Или у вас не рецептурный был препарат?
Языки, которыми пользовалась (турбопаскаль, паскаль + дельфи, пролог) изучала в стародавнее время с помощью бумажных учебников. Сейчас учу питон с помощью гугла, степика и статей на хабре. По-моему, на любой вопрос, который у меня возникает, есть уже статья на хабре. За что, конечно, здешним авторам отдельное спасибо.
Дополню предыдущего оратора относительно степика. Кроме поколения пайтон, очень понравился курс Артема Егорова Инди питон (бесплатный). Этот курс хорошо дополняет продвинутый курс Поколения Пайтон, у Артема замечательные видео. Я их проходила одновременно. Сейчас прохожу егоровский ООП (2 т.р.), все понятно, хорошие тренажеры кода.
Видимо, мы о разных задачах говорим. В реальных задачах оперативного планирования производства есть понятие допустимого решения. Обычно там многокритериальные задачи, большая размерность и от программы ждут, что нажал на кнопку и вышел план, допустимый в каком-то смысле.
Например, отгрузка готовой продукции со склада. Стоит под погрузкой состав, 10 вагонов, за простой - огромный штраф. Как только его отгрузят, подъедет следующий состав. И при этом еще параллельно на складе идет размещение готовой продукции, теми же кранами. И там тоже нужен план. Заказы разбросаны по складу. В условиях договора прописано: заказ отгружается с точностью до 5 тонн. Никому не нужен точный набор или лучшее приближение - как только сгенерировано допустимое решение - формируется план. И тоже самое с госзакупками, правда, здесь задача однокритериальная, нужно не оптимальное решение, а первое решение с допустимым отклонением.
Если мы сейчас обсуждаем мои скромные проекты - спасибо за советы, возможно, когда-нибудь это пригодится. Пока у меня всё работает, в точном соответствии с ТЗ.
Средняя госзакупочная сумма - 10 миллионов рублей. Переводим в копейки - миллиард. Табличка с миллиардом столбиков. Предположим, что точное решение существует. Предположим, что бухгалтер его когда-нибудь дождется. А на самом деле его устроило бы любое решение с отклонением не более, чем 100 руб.
Вот и возникает вопрос - Зачем?
По-моему, вы сами понимаете, что это аппроксимационный алгоритм, потому что пишите про абсолютную погрешность алгоритма.
Я подумаю, понимаю я или еще нет))
Это приближенный алгоритм, у которого абсолютная погрешность фиксирована и не зависит от количества слагаемых и величины набираемой суммы, соответственно, асимптотическая погрешность равна 1. По-моему, для NP-hard лучше не бывает.
Если всё-таки превратить эту задачу в рюкзак. Тогда она будет звучать так. Дано мн-во A предметов, у к-х нецелый вес=стоимость, и дано нецелое число B. Вопрос. Найти рюкзак с суммарным весом <= B и суммарной стоимостью >= B. ДП эту задачу решать нельзя. Для ДП нужна целочисленность хотя бы по одному параметру.
Хорошо, для ДП есть т.н. метод масштабирования. Если попытаться применить его к этой задаче. Вначале придется умножить на 100 (рубли-копейки). Затем всё нужно уменьшить в scale раз, где scale - к-т масштабирования, и отбросить дробную часть. Величина погрешности n*scale, где n - число слагаемых. Для этой задачи scale = 10000 и n = несколько сотен.
Обратите внимание, я не говорю, что ваш алгоритм плох: точные и быстрые аппроксимации - это очень обширная тема исследований и такой алгоритм очень полезен на практике.
Но все же это другой класс алгоритмов. В статье тут рассматривается точный алгоритм.
Спасибо вам на добром слове! Что он плох, мне уже сказал ТС, для к-го я два дня писала статью))
Да, это другой класс алгоритмов, обычная бухгалтерская программа для оптимизационной постановки задачи о наборе суммы. Наверно, было бы странно, если бы бухгалтер запустил программу, она бы прострекотала и сообщила, что решения нет. За сим откланиваюсь. Рюкзак так рюкзак.
Мой модельный пример. Нужно набрать 100; рабочий массив A = [11(10), 8 (20), 3, 2(10)], в круглых скобках указана кратность слагаемого. Результат работы алгоритма - [11(8), 8, 2(2)], набираем ровно 100.
Где в этой задаче вы увидели рюкзак? Не могу понять ход ваших мыслей. Это первое.
Теперь второе. Умный любит учиться, как Антон Павлович Чехов однажды заметил. Покажите, как набрать нецелочисленную сумму порядка 10^7 с помощью нескольких сотен нецелочисленных слагаемых, хоть рюкзаком, хоть ДП, хоть ЦЛП, хоть чем.
У рюкзака каждый элемент имеет вес и стоимость, здесь - только стоимость (просто я называю ее весом, так короче). Если взять целые веса и положить D=0, то получим задачу о наборе заданной суммы. Специально (для вас) взяла модельный целочисленный пример с D=0. Вы до него дочитали?
А вообще в этом нет ничего удивительного, NP-полные задачи друг к другу полиномиально сводятся. Сейчас пишу с телефона, неудобно, доберусь до десктопа, докажу полиномиальную сводимость для Рюкзака и Суммы размеров.
Написала небольшую статью, залила на свой яндекс-диск. P.S. телеграм-канала у меня нет))
https://disk.yandex.ru/i/p_DAaxLI8XwFPw
Про решение СЛАУ я вам ничего сказать не могу.
И спорить в вами не буду, вы правы. Для сверхбольшой размерности делают особые алгоритмы. Пусть будет не сверхбольшая, а большая производственная размерность.
Нет, там не рюкзак, там чистый набор заданной суммы заданными слагаемыми по недостатку (недобрать можно, перебрать нельзя). Программы у меня нет, т.к. писали под какую-то конкретную бухгалтерскую программу. Прям отдельную статью про это писать не хочется (тем более, она опубликована в "Информационных технологиях"), просто выложу сюда описание первой, приближенной части алгоритма. И на примере покажу, как он работает.
Делала два раза подобную задачу в сверхбольшой размерности: при отгрузке листопроката (но там кроме набора заданного веса было ограничение на количество перекладываний в штабелях и дополнительно нужно было освобождать рабочее пространство склада). А вот второй раз при госзакупках нужно было выбрать выделенную на подразделение сумму с помощью списка: товары, их стоимость, требуемое количество. Суммы были огромные, но программа набирала с точностью нескольких рублей (программу писала работающая в бухгалтерии дипломница, алгоритм описан в статье, если кому интересно, дам ссылку). Идея гибридного алгоритма. Основная часть суммы набирается довольно хитрым не совсем жадным алгоритмом, т.к. производятся некоторые возвраты. Добор небольшой суммы не более чем 20 слагаемыми производится точным алгоритмом. Работает быстро и довольно точно, верхняя оценка погрешности величина последнего добавленного слагаемого, числа не целые (рубли, копейки).
Я закончила мехмат в 1982 г. Выпустили половину от набора, особо не отчисляли, у нас был очень хороший начальник курса, Петр Иванович Пасиченко, люди забирали документы и переводились в технические вузы или провинциальные университеты. Из получивших диплом немногие стали "профессиональными" математиками, большая часть стала как раз программистами. И в "ящиках", и в различных НИИ. Даже как-то смешно читать о том, что выпускник мехмата не может стать программистом. Моя близкая подруга, и одноклассница в школе, и одногруппница в МГУ, распределилась в Новосибирский академгородок, стала системным программистом (Эльбрус), потом много лет в Израиле в фирме работала, потом, как говорила Анна Ахматова, "стара собака стала", вернулись с мужем в Новосибирск, до сих делают проекты как фрилансеры.
Что касается детей-вундеркиндов, которых я много повидала и как преподаватель, и как родитель (дочь у меня в 14 лет школу закончила), то на них равняться не надо, жизнь у них тяжёлая, особенно если родители сдуру отправляют их учиться не по возрасту.
Теперь история из жизни. У профессора моей кафедры (по образованию теплотехника, но ставшего программистом), был любимый аспирант, очень одаренный парень, из математической школы. Аспирант успешно защитил кандидатскую, уехал с женой в не резиновую, там не понравилось, нашел фирму в Австралии, прошел тест. Тут из фирмы просят документ об образовании, и он отправил им свой кандидатский диплом. Нет, у нас работа простая, такой квалифицированный нам не нужен. Нашел другую фирму, в Новой Зеландии, прошел тест, собеседование, прислал бакалаврский диплом нашей кафедры - уже давно живёт в Н.З.
Еще раз спасибо. В данный момент я думаю, как переписать свои программы с графами с паскаля на питон. Видимо, питон был не лучший выбор, но не хочется бросать на полпути.
Что касается вашего вопроса о постановке задачи для поиска абсолютного центра. Сейчас открыла статью, вспомнила, какую "реальную" постановку я придумала (придумала, т.к. в редакции просили дать практическое приложение для алгоритма). В качестве вектора весов используются две характеристики ребра: длина и стоимость.
Задача о платных дорогах.
Условие. Дан неор. граф, каждому ребру приписаны положительная длина и положительная стоимость. Вершины взвешены, веса неотр. (вес вершин - "важность" клиентов. Если все клиенты одинаковы, то веса единичные). Задана положительная граница стоимости B. Требуется разместить абсолютный центр (в любой точке графа) так, чтобы стоимость проезда от центра до любого клиента не превосходила B, а взвешенное расстояние до самого удалённого клиента было минимально.
Там целая серия весьма прикладных задач, во-первых разные типы обслуживающих центров (центры - минимизируем расстояние от центра до самого удалённого клиента и медианы - минимизируем сумму расстояний от всех клиентов до центра), в разных вариациях: обслуживающие центры в вершинах или посреди ребра (дуги); клиенты в вершинах или в любой точке ребра (дуги). Один обслуживающий центр размещается за полиномиальное время, далее - NP-hard. Из P нетривиальная задача только одна - размещение абсолютного центра на неор. графе. У нас по старинке её до сих пор графическим алгоритмом Хакими решают, для графа с невзвешенными вершинами.
Я сделала размещение абс. центра с ограничениями (ребру приписан вектор весов), вроде на тот момент не было таких постановок или я плохо искала, во всяком случае, опубликовали в ИТ и ВС в 20-м году. Вот мой список литературы, не знаю, как в спойлер убрать:
1. Hakimi, S.L. 1964. Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph. Operations Research 12:450–459. doi:10.1287/opre.12.3.450.
2. Kariv, O. & Hakimi, S.L. 1979. Algorithmic approach to network location problems, I: The p-Centers, SIAM J. Appl. Math. 37(3):513–537. doi:10.1137/0137040.
3. Goldman, A.J. Minimax location of a facility in a network. Transp. Sci. 6(4):407–418. doi:10.1287/trsc.6.4.407.
4. Megiddo, N. 1983. Linear-time algorithms for linear programming in R3 and related problems. SIAMJ. Comput. 12(4): 759–776. doi:10.1137/0212052.
5. Ding, W. & Qiu., K. 2017. FPTAS for generalized absolute 1-center problem in vertex-weighted graphs. Journal of Combinatorial Optimization. 34(4):1084–1095. doi: 10.1007/s10878-017-0130-4.
6. Ramos, R.M., Sicilia, J. & Ramos, M.T. 1997. The biobjective absolute center problem. TOP, 5(2): 187-199. doi: 10.1007/BF02568548.
7. Ding, W. & Qiu., K. 2015. Approximating the Restricted 1-Center in Graphs. In: Lu Z., Kim D., Wu W., Li W., Du DZ. (eds) Combinatorial Optimization and Applications. Lecture Notes in Computer Science, vol 9486: 647-659. doi: 10.1007/978-3-319-26626-8_47.
8. Minieka, E. 1981. Polynomial Time Algorithm for Finding the Absolute Center of a Network. Networks, 11: 351-355. doi:10.1002/net.3230110404
9. Minieka, E. 1978. Optimization Algorithms for Networks and Graphs. New York: Marcel Dekker. 356 p.
10. Christofides, N. 1975. Graph Theory: Algorithmic Approach. New York: Academic. 400 p.