×

Found 149 Documents (Results 1–100)

On the correlation gap of matroids. (English) Zbl 1528.05012

Del Pia, Alberto (ed.) et al., Integer programming and combinatorial optimization. 24th international conference, IPCO 2023, Madison, WI, USA, June 21–23, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13904, 203-216 (2023).
MSC:  05B35 90C27 91B03
PDFBibTeX XMLCite
Full Text: DOI arXiv

Online non-monotone DR-submodular maximization: 1/4 approximation ratio and sublinear regret. (English) Zbl 07724738

Zhang, Yong (ed.) et al., Computing and combinatorics. 28th international conference, COCOON 2022, Shenzhen, China, October 22–24, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13595, 118-125 (2023).
MSC:  68Rxx
PDFBibTeX XMLCite
Full Text: DOI

Approximation algorithms for capacitated assignment with budget constraints and applications in transportation systems. (English) Zbl 07724736

Zhang, Yong (ed.) et al., Computing and combinatorics. 28th international conference, COCOON 2022, Shenzhen, China, October 22–24, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13595, 94-105 (2023).
MSC:  68Rxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Two-stage submodular maximization under knapsack and matroid constraints. (English) Zbl 07722838

Du, Ding-Zhu (ed.) et al., Theory and applications of models of computation. 17th annual conference, TAMC 2022, Tianjin, China, September 16–18, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13571, 140-154 (2023).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Resource time-sharing for IoT applications with deadlines. (English) Zbl 07722894

Erlebach, Thomas (ed.) et al., Algorithmics of wireless networks. 18th international symposium on algorithmics of wireless networks, ALGOSENSORS 2022, Potsdam, Germany, September 8–9, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13707, 91-107 (2022).
MSC:  68M18 68T40
PDFBibTeX XMLCite
Full Text: DOI

Unified greedy approximability beyond submodular maximization. (English) Zbl 1528.90214

Ljubić, Ivana (ed.) et al., Combinatorial optimization. 7th international symposium, ISCO 2022, virtual event, May 18–20, 2022. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 13526, 299-311 (2022).
MSC:  90C27 90C59
PDFBibTeX XMLCite
Full Text: DOI arXiv

Guarantees for maximization of \(k\)-submodular functions with a knapsack and a matroid constraint. (English) Zbl 1527.90192

Ni, Qiufen (ed.) et al., Algorithmic aspects in information and management. 16th international conference, AAIM 2022, Guangzhou, China, August 13–14, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13513, 156-167 (2022).
MSC:  90C27 68W25 90C59
PDFBibTeX XMLCite
Full Text: DOI

Interactive optimization of submodular functions under matroid constraints. (English) Zbl 07670914

Fotakis, Dimitris (ed.) et al., Algorithmic decision theory. 7th international conference, ADT 2021, Toulouse, France, November 3–5, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13023, 307-322 (2021).
PDFBibTeX XMLCite
Full Text: DOI

The multi-budget maximum weighted coverage problem. (English) Zbl 07667129

Calamoneri, Tiziana (ed.) et al., Algorithms and complexity. 12th international conference, CIAC 2021, virtual event, May 10–12, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12701, 173-186 (2021).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI

Measured continuous greedy with differential privacy. (English) Zbl 1498.90203

Wu, Weili (ed.) et al., Algorithmic aspects in information and management. 15th international conference, AAIM 2021, virtual event, December 20–22, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13153, 212-226 (2021).
PDFBibTeX XMLCite
Full Text: DOI

A multi-pass streaming algorithm for regularized submodular maximization. (English) Zbl 07550563

Du, Ding-Zhu (ed.) et al., Combinatorial optimization and applications. 15th international conference, COCOA 2021, Tianjin, China, December 17–19, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13135, 701-711 (2021).
MSC:  68T20 90C27
PDFBibTeX XMLCite
Full Text: DOI

Maximization of monotone non-submodular functions with a knapsack constraint over the integer lattice. (English) Zbl 07550537

Du, Ding-Zhu (ed.) et al., Combinatorial optimization and applications. 15th international conference, COCOA 2021, Tianjin, China, December 17–19, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13135, 364-373 (2021).
MSC:  68T20 90C27
PDFBibTeX XMLCite
Full Text: DOI

A \((1-e^{-1}-\varepsilon)\)-approximation for the monotone submodular multiple knapsack problem. (English) Zbl 07651183

Grandoni, Fabrizio (ed.) et al., 28th annual European symposium on algorithms. ESA 2020, September 7–9, 2020, Pisa, Italy, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 173, Article 44, 19 p. (2020).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI

Tight approximation bounds for maximum multi-coverage. (English) Zbl 1503.90104

Bienstock, Daniel (ed.) et al., Integer programming and combinatorial optimization. 21st international conference, IPCO 2020, London, UK, June 8–10, 2020, Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12125, 66-77 (2020).
MSC:  90C27 90C59
PDFBibTeX XMLCite
Full Text: DOI

Parallelized maximization of nonsubmodular function subject to a cardinality constraint. (English) Zbl 07336131

Kim, Donghyun (ed.) et al., Computing and combinatorics. 26th international conference, COCOON 2020, Atlanta, GA, USA, August 29–31, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12273, 520-531 (2020).
MSC:  68Rxx
PDFBibTeX XMLCite
Full Text: DOI

(Near) optimal adaptivity gaps for stochastic multi-value probing. (English) Zbl 07650116

Achlioptas, Dimitris (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques, 22nd international conference, APPROX 2019, and 23rd international conference, RANDOM 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, September 20–22, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 145, Article 49, 21 p. (2019).
MSC:  68W20 68W25 90C27
PDFBibTeX XMLCite
Full Text: DOI arXiv

Maximizing covered area in the Euclidean plane with connectivity constraint. (English) Zbl 07650099

Achlioptas, Dimitris (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques, 22nd international conference, APPROX 2019, and 23rd international conference, RANDOM 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, September 20–22, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 145, Article 32, 21 p. (2019).
MSC:  68W20 68W25 90C27
PDFBibTeX XMLCite
Full Text: DOI

Submodular optimization with contention resolution extensions. (English) Zbl 07650070

Achlioptas, Dimitris (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques, 22nd international conference, APPROX 2019, and 23rd international conference, RANDOM 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, September 20–22, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 145, Article 3, 17 p. (2019).
MSC:  68W20 68W25 90C27
PDFBibTeX XMLCite
Full Text: DOI

Towards nearly-linear time algorithms for submodular maximization with a matroid constraint. (English) Zbl 07561547

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 54, 14 p. (2019).
MSC:  68Nxx 68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Tight FPT approximations for \(k\)-median and \(k\)-means. (English) Zbl 07561535

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 42, 14 p. (2019).
MSC:  68Nxx 68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Generalized assignment via submodular optimization with reserved capacity. (English) Zbl 07525506

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 69, 15 p. (2019).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Filter Results by …

Document Type

all top 5

Author

all top 5

Year of Publication

all top 3

Main Field

all top 3

Software