File Pseudopolynomial.h

↰ Parent directory (ADS/intractable)

The pseudopolynomial algorithms of section 19.1 and of the exercises 19.1 to 19.5.

Definition (ADS/intractable/Pseudopolynomial.h)

Detailed Description

An algorithm is pseudopolynomial if its time is a polynomial in the size d of the input and in the largest integer # in it: subsetSumDP() takes :math:` O( n k ) , polynomial if k is bounded by a polynomial in n and exponential in :math: d = O( n log k ) ` otherwise. A problem is strongly NP-complete if it stays NP-complete when # is bounded by a polynomial in d (CRICCA, COMMESSO VIAGGIATORE, 3-PARTIZIONE); none of them has a pseudopolynomial algorithm unless P = NP (Teorema 19.1), while SOMMA DI SOTTOINSIEME, PARTIZIONE and ZAINO are weakly NP-complete and have one.

The scheduling of n programs of times :math:` t_i ` on m processors within d is pseudopolynomial by dynamic programming on the loads of the processors, :math:` O( n ( d + 1 )^m ) ; if a program may be split in intervals, the rule of McNaughton fills the processors one after the other up to :math: d = max{ max_i t_i , sum_i t_i / m } ` in O( n ) time, and the periodic tasks of REAL-TIME SCHEDULING, with :math:` t_i = C_i / T_i ` and d = 1, are scheduled the same way when no priority rule is required.

The contracts [see File Contract.h]: the numbers are not negative and the processors at least one; each solution returned is checked as a postcondition, the preemptive schedule of McNaughton included. The operations are defined in Pseudopolynomial.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 19.1 and exercises 19.1-19.5, https://algoritmicamente.it/materiali/libro/capitoli/cap19.pdf

  1. McNaughton, Scheduling with deadlines and loss functions, Management Science 6(1), 1-12, 1959, doi:10.1287/mnsc.6.1.1

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes

Functions