×

Found 26 Documents (Results 1–26)

Newest Citations Relevance
Chuzhoy, Julia; Dalirrooyfard, Mina; Grinberg, Vadim; Tan, Zihan

A new conjecture on hardness of 2-CSP’s with implications to hardness of densest \(k\)-subgraph and other problems. (English) Zbl 07918359

Kalai, Yael Tauman (ed.), 14th innovations in theoretical computer science conference, ITCS 2023, January 10–13, 2023, MIT, Cambridge, Massachusetts, USA. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 251, Article 38, 23 p. (2023).
MSC:  68Qxx
Cite Review PDF
Full Text: DOI arXiv
Koana, Tomohiro; Komusiewicz, Christian; Nichterlein, André; Sommer, Frank

Covering many (or few) edges with \(k\) vertices in sparse graphs. (English) Zbl 07836609

Berenbrink, Petra (ed.) et al., 39th international symposium on theoretical aspects of computer science, STACS 2022, Marseille, France, virtual conference, March 15–18, 2022. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 219, Article 42, 18 p. (2022).
MSC:  68Qxx
Cite Review PDF
Full Text: DOI arXiv
Bhangale, Amey; Chakraborty, Diptarka; Kumar, Rajendra

Hardness of approximation of (Multi-)LCS over small alphabet. (English) Zbl 07758340

Byrka, Jarosław (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 23rd international conference, APPROX 2020, and 24th international conference, RANDOM 2020, August 17–19, 2020, Virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 176, Article 38, 16 p. (2020).
MSC:  68W20 68W25 90C27
Cite Review PDF
Full Text: DOI arXiv
Chlamtáč, Eden; Manurangsi, Pasin

Sherali-Adams integrality gaps matching the log-density threshold. (English) Zbl 1521.68253

Blais, Eric (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 21st international workshop, APPROX 2018, and 22nd international workshop, RANDOM 2018 August 20–22, 2018, Princeton, USA. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 116, Article 10, 19 p. (2018).
MSC:  68W25 05C42 68R10
Cite Review PDF
Full Text: DOI arXiv
Manurangsi, Pasin; Moshkovitz, Dana

Approximating dense MAX 2-CSPs. (English) Zbl 1375.68220

Garg, Naveen (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. Proceedings of the 18th international workshop on approximation algorithms for combinatorial optimization problems (APPROX 2015) and the 19th international workshop on randomization and computation (RANDOM 2015), Princeton, NJ, USA, August 24–26, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-89-7). LIPIcs – Leibniz International Proceedings in Informatics 40, 396-415 (2015).
MSC:  68W25 05C85 68Q25
Cite Review PDF
Full Text: DOI arXiv
Dinitz, Michael; Kortsarz, Guy; Nutov, Zeev

Improved approximation algorithm for Steiner \(k\)-Forest with nearly uniform weights. (English) Zbl 1360.68902

Jansen, Klaus (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. Proceedings of the 17th international workshop on approximation algorithms for combinatorial optimization problems (APPROX 2014) and the 18th international workshop on randomization and computation (RANDOM 2014), Universitat Politècnica de Catalunya, Barcelona, Spain, September 4–6, 2014. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-74-3). LIPIcs – Leibniz International Proceedings in Informatics 28, 115-127 (2014).
MSC:  68W25 90C27 90C59
Cite Review PDF
Full Text: DOI
Bhaskara, Aditya; Charikar, Moses; Chlamtac, Eden; Feige, Uriel; Vijayaraghavan, Aravindan

Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph. (English) Zbl 1293.05200

Proceedings of the 42nd annual ACM symposium on theory of computing, STOC ’10. Cambridge, MA, USA, June 5–8, 2010. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-817-9). 201-210 (2010).
MSC:  05C42 05C80 05C85 68W25
Cite Review PDF
Full Text: DOI

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