×

Found 262 Documents (Results 1–100)

Containment of UC2RPQ: the hard and easy cases. (English) Zbl 07650987

Lutz, Carsten (ed.) et al., 23rd international conference on database theory, ICDT 2020, Copenhagen, Denmark, March 30 – April 2, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 155, Article 9, 18 p. (2020).
MSC:  68P15
PDFBibTeX XMLCite
Full Text: DOI

Lower bounds for max-cut via semidefinite programming. (English) Zbl 07600797

Kohayakawa, Yoshiharu (ed.) et al., Latin 2020: theoretical informatics. 14th Latin American symposium, São Paulo, Brazil, January 5–8, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12118, 479-490 (2020).
MSC:  68Qxx 68Rxx 68Wxx
PDFBibTeX XMLCite
Full Text: DOI

Simultaneous max-cut is harder to approximate than max-cut. (English) Zbl 07561737

Saraf, Shubhangi (ed.), 35th computational complexity conference, CCC 2020, July 28–31, 2020, Saarbrücken, Germany, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 169, Article 9, 15 p. (2020).
MSC:  68Q25
PDFBibTeX XMLCite
Full Text: DOI

Smoothed complexity of local max-cut and binary max-CSP. (English) Zbl 07298309

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). 1052-1065 (2020).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Lifting sum-of-squares lower bounds: degree-2 to degree-4. (English) Zbl 07298292

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). 840-853 (2020).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Almost optimal classical approximation algorithms for a quantum generalization of max-cut. (English) Zbl 07650098

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 31, 17 p. (2019).
MSC:  68W20 68W25 90C27
PDFBibTeX XMLCite
Full Text: DOI arXiv

Global cardinality constraints make approximating some max-2-CSPs harder. (English) Zbl 07650091

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 24, 17 p. (2019).
MSC:  68W20 68W25 90C27
PDFBibTeX XMLCite
Full Text: DOI arXiv

Sherali-Adams strikes back. (English) Zbl 1528.68318

Shpilka, Amir (ed.), 34th computational complexity conference, CCC 2019, New Brunswick, NJ, USA, July 18–20, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 137, Article 8, 30 p. (2019).
PDFBibTeX XMLCite
Full Text: DOI

An improved fixed-parameter algorithm for max-cut parameterized by crossing number. (English) Zbl 07173542

Colbourn, Charles J. (ed.) et al., Combinatorial algorithms. 30th international workshop, IWOCA 2019, Pisa, Italy, July 23–25, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11638, 327-338 (2019).
MSC:  68Rxx 68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

A bundle approach for SDPs with exact subgraph constraints. (English) Zbl 1436.90100

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, 205-218 (2019).
MSC:  90C22 90C35
PDFBibTeX XMLCite
Full Text: DOI arXiv

An optimal space lower bound for approximating MAX-CUT. (English) Zbl 1433.68621

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). 277-288 (2019).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Adapting local sequential algorithms to the distributed setting. (English) Zbl 1497.68566

Schmid, Ulrich (ed.) et al., 32nd international symposium on distributed computing, DISC 2018, New Orleans, Louisiana, USA, October 15–19, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 121, Article 35, 17 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Maximum cuts in edge-colored graphs. (English) Zbl 1383.05122

Bassino, Frédérique (ed.) et al., LAGOS 2017. Selected papers of the 9th Latin-American algorithms, graphs, and optimization symposium, Marseille, France, September 11–15, 2017. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 62, 87-92 (2017).
MSC:  05C15 05C10 68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Exact separation of \(k\)-projection polytope constraints. (English) Zbl 1383.49014

Takáč, Martin (ed.) et al., Modeling and optimization: theory and applications. MOPTA, Bethlehem, PA, USA, August 17–19, 2016. Selected contributions. Cham: Springer (ISBN 978-3-319-66615-0/hbk; 978-3-319-66616-7/ebook). Springer Proceedings in Mathematics & Statistics 213, 119-141 (2017).
MSC:  49J45 90C11
PDFBibTeX XMLCite
Full Text: DOI

Packing and covering odd cycles in cubic plane graphs with small faces. (English) Zbl 1378.05034

Drmota, Michael (ed.) et al., Extended abstracts of the ninth European conference on combinatorics, graph theory and applications, EuroComb 2017, Vienna, Austria, August 28 – September 1, 2017. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 61, 925-931 (2017).
MSC:  05C10 05C69
PDFBibTeX XMLCite
Full Text: DOI

Local max-cut in smoothed polynomial time. (English) Zbl 1369.68226

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). 429-437 (2017).
MSC:  68Q25 68T20 91A10
PDFBibTeX XMLCite
Full Text: DOI arXiv

Linear kernels and linear-time algorithms for finding large cuts. (English) Zbl 1398.68229

Seok-Hee Hong (ed.), 27th international symposium on algorithms and computation, ISAAC 2016, Sydney, Australia, December 12–14, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-026-2). LIPIcs – Leibniz International Proceedings in Informatics 64, Article 31, 13 p. (2016).
MSC:  68Q25 05C85 68R10
PDFBibTeX XMLCite
Full Text: DOI

The complexity of SIMPLE MAX-CUT on comparability graphs. (English) Zbl 1356.05093

Ceselli, Alberto (ed.) et al., Extended abstracts of the 14th Cologne-Twente workshop on graphs and combinatorial optimization (CTW’16), Gargnano, Italy, June 6–8, 2016. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 55, 161-164 (2016).
MSC:  05C60 05C35
PDFBibTeX XMLCite
Full Text: DOI

Sparsest-cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem. (English) Zbl 1419.90110

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. Lect. Notes Comput. Sci. 9682, 63-76 (2016).
MSC:  90C35 90C27
PDFBibTeX XMLCite
Full Text: DOI

Sketching cuts in graphs and hypergraphs. (English) Zbl 1365.68469

Proceedings of the 6th conference on innovations in theoretical computer science, ITCS’15, Rehovot, Israel, January 11–13, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3333-7). 367-376 (2015).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Selected applications of convex optimization. (English) Zbl 1321.90005

Springer Optimization and Its Applications 103. Beijing: Tsinghua University Press; Berlin: Springer (ISBN 978-7-302-39029-9/pbk; 978-3-662-46355-0/pbk; 978-3-662-46356-7/ebook). x, 140 p. (2015).
PDFBibTeX XMLCite
Full Text: DOI

Social choice, computational complexity, Gaussian geometry, and Boolean functions. (English) Zbl 1375.91074

Jang, Sun Young (ed.) et al., Proceedings of the International Congress of Mathematicians (ICM 2014), Seoul, Korea, August 13–21, 2014. Vol. IV: Invited lectures. Seoul: KM Kyung Moon Sa (ISBN 978-89-6105-807-0/hbk; 978-89-6105-803-2/set). 633-658 (2014).
MSC:  91B14 68Q87 94C10 60G15
PDFBibTeX XMLCite
Full Text: arXiv

Polynomial kernels for \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound. (English) Zbl 1359.68125

Seth, Anil (ed.) et al., 33nd international conference on foundations of software technology and theoretical computer science, FSTTCS 2013, Guwahati, India, December 12–14, 2013. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-64-4). LIPIcs – Leibniz International Proceedings in Informatics 24, 43-54 (2013).
MSC:  68Q25 05C60 05C85
PDFBibTeX XMLCite
Full Text: DOI arXiv

Filter Results by …

Document Type

all top 5

Author

all top 5

Serial

all top 5

Year of Publication

all top 3

Main Field

all top 3

Software