×

Found 8 Documents (Results 1–8)

A PTAS for unsplittable flow on a path. (English) Zbl 07774340

Leonardi, Stefano (ed.) et al., Proceedings of the 54th annual ACM SIGACT symposium on theory of computing, STOC ’22, Rome, Italy June 20–24, 2022. New York, NY: Association for Computing Machinery (ACM). 289-302 (2022).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Faster \((1+ \varepsilon)\)-approximation for unsplittable flow on a path via resource augmentation and back. (English) Zbl 07740904

Mutzel, Petra (ed.) et al., 29th annual European symposium on algorithms. ESA 2021, Lisbon, Portugal (virtual conference), September 6–8, 2021. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 204, Article 49, 15 p. (2021).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI

A \((5/3+\varepsilon)\)-approximation for unsplittable flow on a path: placing small tasks into boxes. (English) Zbl 1422.68298

Diakonikolas, Ilias (ed.) et al., Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC ’18, Los Angeles, CA, USA, June 25–29, 2018. New York, NY: Association for Computing Machinery (ACM). 607-619 (2018).
PDFBibTeX XMLCite
Full Text: DOI

To augment or not to augment: solving unsplittable flow on a path by creating slack. (English) Zbl 1411.68188

Klein, Philip N. (ed.), Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA 2017, Barcelona, Spain, January 16–19, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2411-2422 (2017).
PDFBibTeX XMLCite
Full Text: DOI

Semidefinite and linear programming integrality gaps for scheduling identical machines. (English) Zbl 1402.90054

Louveaux, Quentin (ed.) et al., Integer programming and combinatorial optimization. 18th international conference, IPCO 2016, Liège, Belgium, June 1–3, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-33460-8/pbk; 978-3-319-33461-5/ebook). Lecture Notes in Computer Science 9682, 152-163 (2016).
PDFBibTeX XMLCite
Full Text: DOI

New approximation schemes for unsplittable flow on a path. (English) Zbl 1372.68296

Indyk, Piotr (ed.), Proceedings of the 26th annual ACM-SIAM symposium on discrete algorithms, SODA 2015, Portland, San Diego, CA, January 4–6, 2015. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-374-7; 978-1-61197-373-0/ebook). 47-58 (2015).
MSC:  68W25 05C21 05C85
PDFBibTeX XMLCite
Full Text: DOI

A \((2+\varepsilon)\)-approximation algorithm for the storage allocation problem. (English) Zbl 1440.68336

Halldórsson, Magnús M. (ed.) et al., Automata, languages, and programming. 42nd international colloquium, ICALP 2015, Kyoto, Japan, July 6–10, 2015. Proceedings. Part I. Berlin: Springer. Lect. Notes Comput. Sci. 9134, 973-984 (2015).
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Document Type

all top 5

Year of Publication

Main Field