48 papers
Dit artikel introduceert de eerste benaderingsalgoritmen voor twee generalisaties van het Maximum Quadratic Assignment Problem, namelijk de lijst-beperkte variant en de -matching variant, met respectievelijk een - en een -benadering die asymptotisch aansluiten bij de beste bekende resultaten voor het standaardprobleem.
Dit artikel toont aan dat het robuuste permutatie-flowshop-probleem onder budgettair onzekerheidsmodel in polynomiale tijd kan worden opgelost voor twee machines en benaderd voor een vast aantal machines, door het probleem te reduceren tot het oplossen van een polynomiaal aantal instanties van het nominale probleem.
Dit artikel introduceert een algemeen raamwerk voor positionele s-of-k-spellen, waarbij spelers punten scoren door een bepaald aantal elementen van een winnende verzameling te claimen, en analyseert de behaalde scores op regelmatige roosters onder zowel optimale strategieën als beperkte paarsstrategieën.
Dit artikel introduceert het onderzoek naar minimaal taaiheid in de klasse van zwakke-chordale grafen en biedt volledige classificaties voor diverse subclasses, waaronder co-chordale grafen en complements van bomen, wat bovendien leidt tot eenvoudige bewijzen voor eerdere resultaten op dit gebied.
Dit artikel onderzoekt structurele eigenschappen van kortste flip-sequenties tussen vlakke opspannende bomen in convexe positie en weerlegt de algemene geldigheid van de 'parking edge' en 'reparking' conjecturen, hoewel deze in specifieke gevallen wel opgaan.
Dit artikel presenteert een algebraïsche karakterisering van omkeerbare eerste-grads cellulaire automata over onder de null-randvoorwaarde, waarbij drie noodzakelijke en voldoende voorwaarden worden geïdentificeerd die het mogelijk maken om omkeerbaarheid voor elke roostergrootte in constante tijd te verifiëren of omkeerbare regels te synthetiseren.
Deze paper presenteert een nieuw algoritme met looptijd $2^{O(k \log k)} nk$, en bewijst dat deze complexiteit scherp is onder de Exponentiële Tijd Hypothese.
Deze paper presenteert het eerste multiplicatieve verbetering ten opzichte van de natuurlijke greedy-algoritme voor het maximaliseren van een niet-negatieve monotoon submodulaire functie onder de doorsnede van willekeurige matroiden, door een hybride greedy-locale zoekstrategie te ontwikkelen die een benaderingsratio van ongeveer $0,819k$ bereikt.