×

Found 15 Documents (Results 1–15)

Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs. (English) Zbl 1524.68239

Azar, Yossi (ed.) et al., 26th annual European symposium on algorithms, ESA 2018, August 20–22, 2018, Helsinki, Finland. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 112, Article 65, 13 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI arXiv

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

A \((1+\varepsilon)\)-approximation for unsplittable flow on a path in fixed-parameter running time. (English) Zbl 1441.68291

Chatzigiannakis, Ioannis (ed.) et al., 44th international colloquium on automata, languages, and programming, ICALP 2017, Warsaw, Poland July 10–14, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 80, Article 67, 13 p. (2017).
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 QPTAS for maximum weight independent set of polygons with polylogarithmically many vertices. (English) Zbl 1422.68229

Chekuri, Chandra (ed.), Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms, SODA 2014, Portland, OR, USA, January 5–7, 2014. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 645-656 (2014).
PDFBibTeX XMLCite
Full Text: DOI arXiv

A mazing \(2+\varepsilon\) approximation for unsplittable flow on a path. (English) Zbl 1422.68279

Chekuri, Chandra (ed.), Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms, SODA 2014, Portland, OR, USA, January 5–7, 2014. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 26-41 (2014).
PDFBibTeX XMLCite
Full Text: DOI arXiv

A constant factor approximation algorithm for unsplittable flow on paths. (English) Zbl 1292.68162

Ostrovsky, Rafail (ed.), Proceedings of the 2011 IEEE 52nd annual symposium on foundations of computer science – FOCS 2011, Palm Springs, CA, USA, October 22–25. Los Alamitos, CA: IEEE Computer Society (ISBN 978-0-7695-4571-4; 978-1-4577-1843-4/ebook). 47-56 (2011).
PDFBibTeX XMLCite
Full Text: DOI

Local algorithms for edge colorings in UDGs. (English) Zbl 1273.68279

Paul, Christophe (ed.) et al., Graph-theoretic concepts in computer science. 35th international workshop, WG 2009, Montpellier, France, June 24–26, 2009. Revised papers. Berlin: Springer (ISBN 978-3-642-11408-3/pbk). Lecture Notes in Computer Science 5911, 202-213 (2010).
MSC:  68R10 05C15 05C85
PDFBibTeX XMLCite
Full Text: DOI

Local PTAS for dominating and connected dominating set in location aware unit disk graphs. (English) Zbl 1209.68655

Bampis, Evripidis (ed.) et al., Approximation and online algorithms. 6th international workshop, WAOA 2008, Karlsruhe, Germany, September 18–19, 2008. Revised papers. Berlin: Springer (ISBN 978-3-540-93979-5/pbk). Lecture Notes in Computer Science 5426, 227-240 (2009).
MSC:  68W25 05C69 05C85
PDFBibTeX XMLCite
Full Text: DOI

Local construction and coloring of spanners of location aware unit disk graphs (extended abstract). (English) Zbl 1202.05048

Broersma, Hajo (ed.) et al., Graph-theoretic concepts in computer science. 34th international workshop, WG 2008, Durham, UK, June 30–July 2, 2008. Revised papers. Berlin: Springer (ISBN 978-3-540-92247-6/pbk). Lecture Notes in Computer Science 5344, 372-383 (2008).
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Document Type

all top 5

Year of Publication

Main Field