Other formats:
BibTeX
LaTeX
RIS
@inproceedings{1648276, author = {Eiben, Eduard and Ganian, Robert and Knop, Dusan and Ordyniak, Sebastian and Pilipczuk, Michal and Wrochna, Marcin}, address = {USA}, booktitle = {Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019}, doi = {http://dx.doi.org/10.1007/978-3-030-17953-3_15}, editor = {Andrea Lodi and Viswanath Nagarajan}, keywords = {Parameterized Complexity}, howpublished = {elektronická verze "online"}, language = {eng}, location = {USA}, isbn = {978-3-030-17952-6}, pages = {194-204}, publisher = {Springer}, title = {Integer Programming and Incidence Treedepth}, url = {https://link.springer.com/chapter/10.1007%2F978-3-030-17953-3_15}, year = {2019} }
TY - JOUR ID - 1648276 AU - Eiben, Eduard - Ganian, Robert - Knop, Dusan - Ordyniak, Sebastian - Pilipczuk, Michal - Wrochna, Marcin PY - 2019 TI - Integer Programming and Incidence Treedepth PB - Springer CY - USA SN - 9783030179526 KW - Parameterized Complexity UR - https://link.springer.com/chapter/10.1007%2F978-3-030-17953-3_15 L2 - https://link.springer.com/chapter/10.1007%2F978-3-030-17953-3_15 N2 - Recently a strong connection has been shown between the tractability of integer programming (IP) with bounded coefficients on the one side and the structure of its constraint matrix on the other side. To that end, integer linear programming is fixed-parameter tractable with respect to the primal (or dual) treedepth of the Gaifman graph of its constraint matrix and the largest coefficient (in absolute value). Motivated by this, Koutecký, Levin, and Onn [ICALP 2018] asked whether it is possible to extend these result to a more broader class of integer linear programs. More formally, is integer linear programming fixed-parameter tractable with respect to the incidence treedepth of its constraint matrix and the largest coefficient (in absolute value)? We answer this question in negative. ER -
EIBEN, Eduard, Robert GANIAN, Dusan KNOP, Sebastian ORDYNIAK, Michal PILIPCZUK and Marcin WROCHNA. Integer Programming and Incidence Treedepth. Online. In Andrea Lodi and Viswanath Nagarajan. \textit{Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019}. USA: Springer, 2019, p.~194-204. ISBN~978-3-030-17952-6. Available from: https://dx.doi.org/10.1007/978-3-030-17953-3\_{}15.
|