Exponential Tightness For Integral Type Functionals Of Centered Independent Differently Distributed Random Variables

Standard

Exponential Tightness For Integral Type Functionals Of Centered Independent Differently Distributed Random Variables. / Logachov, A. V.; Mogulskii, A. A.

в: Siberian Electronic Mathematical Reports, Том 19, № 1, 2022, стр. 273-284.

Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование

BibTeX

@article{1dc7f17cf3004ce3babafa7882c0c421,

title = "Exponential Tightness For Integral Type Functionals Of Centered Independent Differently Distributed Random Variables",

abstract = "In the routing open shop problem a fleet of mobile machines has to traverse the given transportation network, to process immovable jobs located at its nodes and to return back to the initial location in the shortest time possible. The problem is known to be NP-hard even for the simplest case with two machines and two nodes. We consider a special proportionate case of this problem, in which processing time for any job does not depend on a machine. We prove that the problem in this simplified setting is still NP-hard for the same simplest case. To that end, we introduce the new problem we call 2-Summing and reduce it to the problem under consideration. We also suggest a (Formula presented)-approximation algorithm for the two-machine proportionate problem with at most three nodes.",

keywords = "approximation algorithm, complexity, optima localization, proportionate open shop, routing open shop, standard lower bound",

author = "Logachov, {A. V.} and Mogulskii, {A. A.}",

note = "The work is supported by Mathematical Center in Akademgorodok under agreement No. 07515-2022-282 with the Ministry of Science and Higher Education of the Russian Federation.",

year = "2022",

doi = "10.33048/semi.2022.19.021",

language = "English",

volume = "19",

pages = "273--284",

journal = "Сибирские электронные математические известия",

issn = "1813-3304",

publisher = "Sobolev Institute of Mathematics",

number = "1",

}

RIS

TY - JOUR

T1 - Exponential Tightness For Integral Type Functionals Of Centered Independent Differently Distributed Random Variables

AU - Logachov, A. V.

AU - Mogulskii, A. A.

N1 - The work is supported by Mathematical Center in Akademgorodok under agreement No. 07515-2022-282 with the Ministry of Science and Higher Education of the Russian Federation.

PY - 2022

Y1 - 2022

N2 - In the routing open shop problem a fleet of mobile machines has to traverse the given transportation network, to process immovable jobs located at its nodes and to return back to the initial location in the shortest time possible. The problem is known to be NP-hard even for the simplest case with two machines and two nodes. We consider a special proportionate case of this problem, in which processing time for any job does not depend on a machine. We prove that the problem in this simplified setting is still NP-hard for the same simplest case. To that end, we introduce the new problem we call 2-Summing and reduce it to the problem under consideration. We also suggest a (Formula presented)-approximation algorithm for the two-machine proportionate problem with at most three nodes.

AB - In the routing open shop problem a fleet of mobile machines has to traverse the given transportation network, to process immovable jobs located at its nodes and to return back to the initial location in the shortest time possible. The problem is known to be NP-hard even for the simplest case with two machines and two nodes. We consider a special proportionate case of this problem, in which processing time for any job does not depend on a machine. We prove that the problem in this simplified setting is still NP-hard for the same simplest case. To that end, we introduce the new problem we call 2-Summing and reduce it to the problem under consideration. We also suggest a (Formula presented)-approximation algorithm for the two-machine proportionate problem with at most three nodes.

KW - approximation algorithm

KW - complexity

KW - optima localization

KW - proportionate open shop

KW - routing open shop

KW - standard lower bound

UR - https://elibrary.ru/item.asp?id=49384633

UR - https://www.mendeley.com/catalogue/4f669ace-154c-3665-8415-f0e3e56985de/

U2 - 10.33048/semi.2022.19.021

DO - 10.33048/semi.2022.19.021

M3 - Article

VL - 19

SP - 273

EP - 284

JO - Сибирские электронные математические известия

JF - Сибирские электронные математические известия

SN - 1813-3304

IS - 1

ER -

ID: 63640209