×

zbMATH — the first resource for mathematics

Found 294 Documents (Results 1–100)

Hits per Page
100
Display Format
MathJax
Result Sorting
Newest 1st
Christodoulou, George; Koutsoupias, Elias; Kovács, Annamária
On the Nisan-Ronen conjecture for submodular valuations. (English) Zbl 07298312
Makarychev, Konstantin (ed.) et al., Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing, STOC ’20, Chicago, IL, USA, June 22–26, 2020. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-6979-4). 1086-1096 (2020).
MSC:  68Qxx
PDF BibTeX XML Cite
\textit{G. Christodoulou} et al., in: Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing, STOC '20, Chicago, IL, USA, June 22--26, 2020. New York, NY: Association for Computing Machinery (ACM). 1086--1096 (2020; Zbl 07298312)
Full Text: DOI
Li, Wenzheng; Liu, Paul; Vondrák, Jan
A polynomial lower bound on adaptive complexity of submodular maximization. (English) Zbl 07298237
Makarychev, Konstantin (ed.) et al., Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing, STOC ’20, Chicago, IL, USA, June 22–26, 2020. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-6979-4). 140-152 (2020).
MSC:  68Qxx
PDF BibTeX XML Cite
\textit{W. Li} et al., in: Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing, STOC '20, Chicago, IL, USA, June 22--26, 2020. New York, NY: Association for Computing Machinery (ACM). 140--152 (2020; Zbl 07298237)
Full Text: DOI
Yang, Ruiqi; Xu, Dachuan; Guo, Longkun; Zhang, Dongmei
Sequence submodular maximization meets streaming. (English) Zbl 1443.90306
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, 565-575 (2019).
MSC:  90C27 90C35 90C59
PDF BibTeX XML Cite
\textit{R. Yang} et al., Lect. Notes Comput. Sci. 11949, 565--575 (2019; Zbl 1443.90306)
Full Text: DOI
Buchbinder, Niv; Feldman, Moran; Filmus, Yuval; Garg, Mohit
Online submodular maximization: beating 1/2 made simple. (English) Zbl 1436.90134
Lodi, Andrea (ed.) et al., Integer programming and combinatorial optimization. 20th international conference, IPCO 2019, Ann Arbor, MI, USA, May 22–24, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11480, 101-114 (2019).
MSC:  90C30 91B26
PDF BibTeX XML Cite
\textit{N. Buchbinder} et al., Lect. Notes Comput. Sci. 11480, 101--114 (2019; Zbl 1436.90134)
Full Text: DOI
Chen, Lin; Feldman, Moran; Karbasi, Amin
Unconstrained submodular maximization with constant adaptive complexity. (English) Zbl 1433.68592
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). 102-113 (2019).
MSC:  68W10 68W25 90C27
PDF BibTeX XML Cite
\textit{L. Chen} et al., in: 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). 102--113 (2019; Zbl 1433.68592)
Full Text: DOI
Ene, Alina; Nguyễn, Huy L.; Vladu, Adrian
Submodular maximization with matroid and packing constraints in parallel. (English) Zbl 1433.68593
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). 90-101 (2019).
MSC:  68W10 68W25 68W40 90C27
PDF BibTeX XML Cite
\textit{A. Ene} et al., in: 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). 90--101 (2019; Zbl 1433.68593)
Full Text: DOI
Chekuri, Chandra; Quanrud, Kent
Parallelizing greedy for submodular set function maximization in matroids and beyond. (English) Zbl 1433.68591
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). 78-89 (2019).
MSC:  68W10 68W20 68W25 90C27
PDF BibTeX XML Cite
\textit{C. Chekuri} and \textit{K. Quanrud}, in: 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). 78--89 (2019; Zbl 1433.68591)
Full Text: DOI
Balkanski, Eric; Rubinstein, Aviad; Singer, Yaron
An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model. (English) Zbl 1433.68590
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). 66-77 (2019).
MSC:  68W10 68W25 90C27
PDF BibTeX XML Cite
\textit{E. Balkanski} et al., in: 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). 66--77 (2019; Zbl 1433.68590)
Full Text: DOI
Huang, Chien-Chung; Kakimura, Naonori
Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint. (English) Zbl 1435.68388
Friggstad, Zachary (ed.) et al., Algorithms and data structures. 16th international symposium, WADS 2019, Edmonton, AB, Canada, August 5–7, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11646, 438-451 (2019).
MSC:  68W27 68W25 90C27
PDF BibTeX XML Cite
\textit{C.-C. Huang} and \textit{N. Kakimura}, Lect. Notes Comput. Sci. 11646, 438--451 (2019; Zbl 1435.68388)
Full Text: DOI
Buchbinder, Niv; Feldman, Moran; Garg, Mohit
Deterministic \((\frac12 + \varepsilon)\)-approximation for submodular maximization over a matroid. (English) Zbl 1431.90125
Chan, Timothy M. (ed.), Proceedings of the 30th annual ACM-SIAM symposium on discrete algorithms, SODA 2019, San Diego, CA, USA, January 6–9, 2019. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 241-254 (2019).
MSC:  90C27 68W25
PDF BibTeX XML Cite
\textit{N. Buchbinder} et al., in: Proceedings of the 30th annual ACM-SIAM symposium on discrete algorithms, SODA 2019, San Diego, CA, USA, January 6--9, 2019. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 241--254 (2019; Zbl 1431.90125)
Full Text: DOI
Balkanski, Eric; Singer, Yaron
The adaptive complexity of maximizing a submodular function. (English) Zbl 1427.68365
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). 1138-1151 (2018).
MSC:  68W25 68W10 90C27
PDF BibTeX XML Cite
\textit{E. Balkanski} and \textit{Y. Singer}, in: 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). 1138--1151 (2018; Zbl 1427.68365)
Full Text: DOI
Nägele, Martin; Sudakov, Benny; Zenklusen, Rico
Submodular minimization under congruency constraints. (English) Zbl 1403.68385
Czumaj, Artur (ed.), Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms, SODA 2018, New Orleans, LA, USA, January 7–10, 2018. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-503-1/ebook). 849-866 (2018).
MSC:  68W40 05B35 90C27
PDF BibTeX XML Cite
\textit{M. Nägele} et al., in: Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms, SODA 2018, New Orleans, LA, USA, January 7--10, 2018. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 849--866 (2018; Zbl 1403.68385)
Full Text: Link arXiv
Kutiel, Gilad; Rawitz, Dror
Local search algorithms for maximum carpool matching problem. (English) Zbl 1442.68267
Pruhs, Kirk (ed.) et al., 25th European symposium on algorithms, ESA 2017, Vienna, Austria, September 4–6, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 87, Article 55, 14 p. (2017).
MSC:  68W25 05C20 05C70 68Q17 90C27 91B68
PDF BibTeX XML Cite
\textit{G. Kutiel} and \textit{D. Rawitz}, LIPIcs -- Leibniz Int. Proc. Inform. 87, Article 55, 14 p. (2017; Zbl 1442.68267)
Full Text: DOI
Chan, T.-H. Hubert; Jiang, Shaofeng H.-C.; Tang, Zhihao Gavin; Wu, Xiaowei
Online submodular maximization problem with vector packing constraint. (English) Zbl 1442.68272
Pruhs, Kirk (ed.) et al., 25th European symposium on algorithms, ESA 2017, Vienna, Austria, September 4–6, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 87, Article 24, 14 p. (2017).
MSC:  68W27 90C27
PDF BibTeX XML Cite
\textit{T. H. H. Chan} et al., LIPIcs -- Leibniz Int. Proc. Inform. 87, Article 24, 14 p. (2017; Zbl 1442.68272)
Full Text: DOI
Hanifehnezhad, Saeid; Dolati, Ardeshir
Gomory Hu tree and pendant pairs of a symmetric submodular system. (English) Zbl 1440.90059
Mousavi, Mohammad Reza (ed.) et al., Topics in theoretical computer science. Second IFIP WG 1.8 international conference, TTCS 2017, Tehran, Iran, September 12–14, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10608, 26-33 (2017).
MSC:  90C27
PDF BibTeX XML Cite
\textit{S. Hanifehnezhad} and \textit{A. Dolati}, Lect. Notes Comput. Sci. 10608, 26--33 (2017; Zbl 1440.90059)
Full Text: DOI
Goemans, Michel X.; Gupta, Swati; Jaillet, Patrick
Discrete Newton’s algorithm for parametric submodular function minimization. (English) Zbl 1418.90226
Eisenbrand, Friedrich (ed.) et al., Integer programming and combinatorial optimization. 19th international conference, IPCO 2017, Waterloo, ON, Canada, June 26–28, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10328, 212-227 (2017).
MSC:  90C27 90C32 90C53
PDF BibTeX XML Cite
\textit{M. X. Goemans} et al., Lect. Notes Comput. Sci. 10328, 212--227 (2017; Zbl 1418.90226)
Full Text: DOI
Chakrabarty, Deeparnab; Lee, Yin Tat; Sidford, Aaron; Wong, Sam Chiu-wai
Subquadratic submodular function minimization. (English) Zbl 1370.90206
Hatami, Hamed (ed.) et al., Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC ’17, Montreal, QC, Canada, June 19–23, 2017. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4528-6). 1220-1231 (2017).
MSC:  90C27 90C59 90C60
PDF BibTeX XML Cite
\textit{D. Chakrabarty} et al., in: Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC '17, Montreal, QC, Canada, June 19--23, 2017. New York, NY: Association for Computing Machinery (ACM). 1220--1231 (2017; Zbl 1370.90206)
Full Text: DOI
van Heuven van Staereling, Irving; de Keijzer, Bart; Schäfer, Guido
The ground-set-cost budgeted maximum coverage problem. (English) Zbl 1398.91302
Faliszewski, Piotr (ed.) et al., 41st international symposium on mathematical foundations of computer science, MFCS 2016, Kraków, Poland, August 22–26, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-016-3). LIPIcs – Leibniz International Proceedings in Informatics 58, Article 50, 13 p. (2016).
MSC:  91B26 68W25 05C15
PDF BibTeX XML Cite
\textit{I. van Heuven van Staereling} et al., LIPIcs -- Leibniz Int. Proc. Inform. 58, Article 50, 13 p. (2016; Zbl 1398.91302)
Full Text: DOI
Hirai, Hiroshi; Oki, Taihei
A compact representation for minimizers of \(k\)-submodular functions (extended abstract). (English) Zbl 1455.90134
Cerulli, Raffaele (ed.) et al., Combinatorial optimization. 4th international symposium, ISCO 2016, Vietri sul Mare, Italy, May 16–18, 2016. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 9849, 381-392 (2016).
Reviewer: Svetlana A. Kravchenko (Minsk)
MSC:  90C27 90-06 06-08 06A11 06A12
PDF BibTeX XML Cite
\textit{H. Hirai} and \textit{T. Oki}, Lect. Notes Comput. Sci. 9849, 381--392 (2016; Zbl 1455.90134)
Full Text: DOI
Iwamasa, Yuni
On a general framework for network representability in discrete optimization (extended abstract). (English) Zbl 1452.90222
Cerulli, Raffaele (ed.) et al., Combinatorial optimization. 4th international symposium, ISCO 2016, Vietri sul Mare, Italy, May 16–18, 2016. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 9849, 369-380 (2016).
MSC:  90C10 90B10 90C27
PDF BibTeX XML Cite
\textit{Y. Iwamasa}, Lect. Notes Comput. Sci. 9849, 369--380 (2016; Zbl 1452.90222)
Full Text: DOI

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