The Library
Exponential-time approximation schemes via compression
Tools
Inamdar, Tanmay, Kundu, Madhumita, Parviainen, Pekka, Ramanujan, Maadapuzhi Sridharan and Saurabh, Saket (2024) Exponential-time approximation schemes via compression. In: 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), Berkeley, CA, USA, 30 Jan - 2 Feb 2024. Published in: 5th Innovations in Theoretical Computer Science Conference (ITCS 2024), 287 64:1-64:22. doi:10.4230/LIPIcs.ITCS.2024.64
|
PDF
LIPIcs.ITCS.2024.64.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (944Kb) | Preview |
Official URL: https://doi.org/10.4230/LIPIcs.ITCS.2024.64
Abstract
In this paper, we give a framework to design exponential-time approximation schemes for basic graph partitioning problems such as k-way cut, Multiway Cut, Steiner k-cut and Multicut, where the goal is to minimize the number of edges going across the parts. Our motivation to focus on approximation schemes for these problems comes from the fact that while it is possible to solve them exactly in 2^nn^{{
Item Type: | Conference Item (Paper) | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||||||
Library of Congress Subject Headings (LCSH): | Computer algorithms, Algorithms, Graph algorithms, Computational complexity | ||||||||||||
Series Name: | Leibniz International Proceedings in Informatics (LIPIcs) | ||||||||||||
Journal or Publication Title: | 5th Innovations in Theoretical Computer Science Conference (ITCS 2024) | ||||||||||||
Publisher: | Schloss Dagstuhl — Leibniz-Zentrum für Informatik | ||||||||||||
Place of Publication: | Dagstuhl, Germany | ||||||||||||
Official Date: | 24 January 2024 | ||||||||||||
Dates: |
|
||||||||||||
Volume: | 287 | ||||||||||||
Page Range: | 64:1-64:22 | ||||||||||||
DOI: | 10.4230/LIPIcs.ITCS.2024.64 | ||||||||||||
Status: | Peer Reviewed | ||||||||||||
Publication Status: | Published | ||||||||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||||||||
Date of first compliant deposit: | 24 January 2024 | ||||||||||||
Date of first compliant Open Access: | 25 January 2024 | ||||||||||||
RIOXX Funder/Project Grant: |
|
||||||||||||
Conference Paper Type: | Paper | ||||||||||||
Title of Event: | 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) | ||||||||||||
Type of Event: | Conference | ||||||||||||
Location of Event: | Berkeley, CA, USA | ||||||||||||
Date(s) of Event: | 30 Jan - 2 Feb 2024 | ||||||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year