×

Found 742 Documents (Results 1–100)

100
MathJax

A constant-factor approximation algorithm for red-blue set cover with unit disks. (English) Zbl 07495128

Kaklamanis, Christos (ed.) et al., Approximation and online algorithms. 18th international workshop, WAOA 2020, virtual event, September 9–10, 2020. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 12806, 204-219 (2021).
MSC:  68W25 68W27
PDF BibTeX XML Cite
Full Text: DOI

Tight bounds on subexponential time approximation of set cover and related problems. (English) Zbl 07495125

Kaklamanis, Christos (ed.) et al., Approximation and online algorithms. 18th international workshop, WAOA 2020, virtual event, September 9–10, 2020. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 12806, 159-173 (2021).
MSC:  68W25 68W27
PDF BibTeX XML Cite
Full Text: DOI arXiv

Multi-cover inequalities for totally-ordered multiple knapsack sets. (English) Zbl 1482.90180

Singh, Mohit (ed.) et al., Integer programming and combinatorial optimization. 22nd international conference, IPCO 2021, Atlanta, GA, USA, May 19–21, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12707, 193-207 (2021).
MSC:  90C27
PDF BibTeX XML Cite
Full Text: DOI arXiv

On the geometric red-blue set cover problem. (English) Zbl 07405957

Uehara, Ryuhei (ed.) et al., WALCOM: algorithms and computation. 15th international conference and workshops, WALCOM 15, Yangon, Myanmar, February 28 – March 2, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12635, 129-141 (2021).
MSC:  68Wxx
PDF BibTeX XML Cite
Full Text: DOI

Reducing graph transversals via edge contractions. (English) Zbl 07559435

Esparza, Javier (ed.) et al., 45th international symposium on mathematical foundations of computer science, MFCS 2020, August 25–26, 2020, Prague, Czech Republic. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 170, Article 64, 15 p. (2020).
MSC:  68Qxx
PDF BibTeX XML Cite
Full Text: DOI

Approximation algorithm for stochastic set cover problem. (English) Zbl 1482.68277

Zhang, Zhao (ed.) et al., Algorithmic aspects in information and management. 14th international conference, AAIM 2020, Jinhua, China, August 10–12, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12290, 37-48 (2020).
PDF BibTeX XML Cite
Full Text: DOI

Precedence-constrained scheduling and min-sum set cover (extended Abstract). (English) Zbl 07238566

Bampis, Evripidis (ed.) et al., Approximation and online algorithms. 17th international workshop, WAOA 2019, Munich, Germany, September 12–13, 2019. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 11926, 170-187 (2020).
MSC:  68W25 68W27
PDF BibTeX XML Cite
Full Text: DOI

Packing and covering with segments. (English) Zbl 07224284

Rahman, M. Sohel (ed.) et al., WALCOM: algorithms and computation. 14th international conference, WALCOM 2020, Singapore, Singapore, March 31 – April 2, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12049, 198-210 (2020).
MSC:  68Wxx
PDF BibTeX XML Cite
Full Text: DOI

Parameterized dynamic variants of red-blue dominating set. (English) Zbl 1440.68134

Chatzigeorgiou, Alexander (ed.) et al., SOFSEM 2020: theory and practice of computer science. 46th international conference on current trends in theory and practice of informatics, SOFSEM 2020, Limassol, Cyprus, January 20–24, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12011, 236-247 (2020).
MSC:  68Q27 05C69
PDF BibTeX XML Cite
Full Text: DOI Link

Faster FPT algorithm for 5-path vertex cover. (English) Zbl 07561676

Rossmanith, Peter (ed.) et al., 44th international symposium on mathematical foundations of computer science, MFCS 2019, Aachen, Germany, August 26–30, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 138, Article 32, 13 p. (2019).
MSC:  68Qxx
PDF BibTeX XML Cite
Full Text: DOI

A simple gap-producing reduction for the parameterized set cover problem. (English) Zbl 07561574

Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 81, 15 p. (2019).
MSC:  68Nxx 68Qxx
PDF BibTeX XML Cite
Full Text: DOI

Fine-grained reductions and quantum speedups for dynamic programming. (English) Zbl 07561501

Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 8, 13 p. (2019).
MSC:  68Nxx 68Qxx
PDF BibTeX XML Cite
Full Text: DOI

The set cover conjecture and subgraph isomorphism with a tree pattern. (English) Zbl 07559154

Niedermeier, Rolf (ed.) et al., 36th international symposium on theoretical aspects of computer science, STACS 2019, March 13–16, 2019, Berlin, Germany. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 126, Article 45, 15 p. (2019).
MSC:  68Qxx
PDF BibTeX XML Cite
Full Text: DOI

Online disjoint set cover without prior knowledge. (English) Zbl 07525481

Bender, Michael A. (ed.) et al., 27th annual European symposium on algorithms, ESA 2019, Munich/Garching, Germany, September 9–11, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 144, Article 44, 16 p. (2019).
MSC:  68Wxx
PDF BibTeX XML Cite
Full Text: DOI

On geometric set cover for orthants. (English) Zbl 07525463

Bender, Michael A. (ed.) et al., 27th annual European symposium on algorithms, ESA 2019, Munich/Garching, Germany, September 9–11, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 144, Article 26, 18 p. (2019).
MSC:  68Wxx
PDF BibTeX XML Cite
Full Text: DOI

Bilu-Linial stability, certified algorithms and the independent set problem. (English) Zbl 07525444

Bender, Michael A. (ed.) et al., 27th annual European symposium on algorithms, ESA 2019, Munich/Garching, Germany, September 9–11, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 144, Article 7, 16 p. (2019).
MSC:  68Wxx
PDF BibTeX XML Cite
Full Text: DOI

Optimal distributed covering algorithms. (English) Zbl 07298661

Nowak, Thomas (ed.), Proceedings of the 38th ACM symposium on principles of distributed computing, PODC ’19, Toronto, ON, Canada, July 29 – August 2, 2019. New York, NY: Association for Computing Machinery (ACM). 104-106 (2019).
MSC:  68M14 68W15
PDF BibTeX XML Cite
Full Text: DOI arXiv Link

An efficient algorithm for combining verification and validation methods. (English) Zbl 1444.68054

Catania, Barbara (ed.) et al., SOFSEM 2019: theory and practice of computer science. 45th international conference on current trends in theory and practice of computer science, Nový Smokovec, Slovakia, January 27–30, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11376, 324-340 (2019).
MSC:  68N30 68Q27 68W40
PDF BibTeX XML Cite
Full Text: DOI

New results on a family of geometric hitting set problems in the plane. (English) Zbl 1435.68350

Li, Yingshu (ed.) et al., Combinatorial optimization and applications. 13th international conference, COCOA 2019, Xiamen, China, December 13–15, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11949, 387-399 (2019).
MSC:  68U05 68Q17 68W25
PDF BibTeX XML Cite
Full Text: DOI

Dynamic set cover: improved algorithms and lower bounds. (English) Zbl 1433.68616

Charikar, Moses (ed.) et al., Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC ’19, Phoenix, AZ, USA, June 23–26, 2019. New York, NY: Association for Computing Machinery (ACM). 114-125 (2019).
PDF BibTeX XML Cite
Full Text: DOI arXiv

Minimum membership covering and hitting. (English) Zbl 07117341

Das, Gautam K. (ed.) et al., WALCOM: algorithms and computation. 13th international conference, WALCOM 2019, Guwahati, India, February 27 – March 2, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11355, 394-406 (2019).
MSC:  68Wxx
PDF BibTeX XML Cite
Full Text: DOI

Covering and packing of rectilinear subdivision. (English) Zbl 07117340

Das, Gautam K. (ed.) et al., WALCOM: algorithms and computation. 13th international conference, WALCOM 2019, Guwahati, India, February 27 – March 2, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11355, 381-393 (2019).
MSC:  68Wxx
PDF BibTeX XML Cite
Full Text: DOI arXiv

Maximum independent and disjoint coverage. (English) Zbl 07117274

Gopal, T. V. (ed.) et al., Theory and applications of models of computation. 15th annual conference, TAMC 2019, Kitakyushu, Japan, April 13–16, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11436, 134-153 (2019).
MSC:  68Q05
PDF BibTeX XML Cite
Full Text: DOI

A local search \(4/3\)-approximation algorithm for the minimum 3-path partition problem. (English) Zbl 07116311

Chen, Yijia (ed.) et al., Frontiers in algorithmics. 13th international workshop, FAW 2019, Sanya, China, April 29 – May 3, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11458, 14-25 (2019).
MSC:  68Wxx
PDF BibTeX XML Cite
Full Text: DOI arXiv

Filter Results by …

Document Type

Reviewing State

all top 5

Author

all top 5

Serial

all top 5

Year of Publication

all top 3

Classification

all top 3

Software