Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

Orbit-finite linear programming

Uproszczony widok
dc.abstract.enAn infinite set is orbit-finite if, up to permutations of the underlying structure of atoms, it has only finitely many elements. We study a generalisation of linear programming where constraints are expressed by an orbit-finite system of linear inequalities. As our principal contribution we provide a decision procedure for checking if such a system has a real solution, and for computing the minimal/maximal value of a linear objective function over the solution set. We also show undecidability of these problems in case when only integer solutions are considered. Therefore orbit-finite linear programming is decidable, while orbit-finite integer linear programming is not.
dc.affiliationUniwersytet Warszawski
dc.conference.countryStany Zjednoczone
dc.conference.datefinish2023-06-29
dc.conference.datestart2023-06-26
dc.conference.placeBoston
dc.conference.seriesIEEE Symposium on Logic in Computer Science
dc.conference.seriesIEEE Symposium on Logic in Computer Science
dc.conference.seriesshortcutLICS
dc.conference.shortcutLICS 2023
dc.conference.weblinkhttps://lics.siglog.org/lics23/
dc.contributor.authorLasota, Sławomir
dc.contributor.authorHofman, Piotr
dc.contributor.authorGhosh, Arka
dc.date.accessioned2024-01-25T16:09:05Z
dc.date.available2024-01-25T16:09:05Z
dc.date.issued2023
dc.description.financePublikacja bezkosztowa
dc.identifier.doi10.1109/LICS56636.2023.10175799
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/115029
dc.identifier.weblinkhttp://xplorestaging.ieee.org/ielx7/10175635/10175671/10175799.pdf?arnumber=10175799
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages1-14
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.titleOrbit-finite linear programming
dc.typeJournalArticle
dspace.entity.typePublication