I detta dokument behandlas problemet med att utforma snabba, ungefärliga, kombinatoriska algoritmer för multicommodity ows och andra fraktionerade förpackningsproblem. Vi erbjuder en annan syn på dessa problem som ger snabbare och mycket enklare algoritmer. I synnerhet ger vi rst polynom-tid, kombinatorial approximation algoritm för bråkiga förpackningsproblem; i själva verket är körtiden för vår algoritm starkt polynom. Vårt tillvägagångssätt tillåter oss också att ersätta kortaste vägberäkningar för min-kostnad ow beräkningar i beräkning maximal samtidig ow och min-kostnad multicommodity ow; detta ger mycket snabbare algoritmer när antalet varor är stort.
Med hjälp av Garg-Könemann approximationsalgoritm REF ger de en (1+ ) (1+2 lnn) approximation av problemet, där n är antalet sensorer.
Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
{'venue': 'SIAM J. Comput.', 'journal': 'SIAM J. Comput.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}