Parinya Chalermsook

Seth Pettie

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023

Parameterized Approximation: Algorithms and Hardness (Dagstuhl Seminar 23291).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2023

The Group Access Bounds for Binary Search Trees.

[BibT_eX]

[DOI]

CoRR, 2023

Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces.

[BibT_eX]

[DOI]

CoRR, 2023

Independent Set in k-Claw-Free Graphs: Conditional χ-Boundedness and the Power of LP/SDP Relaxations.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms - 21st International Workshop, 2023

Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomposition.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Parameterized Approximation Schemes for Clustering with General Norm Objectives.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Polynomial-Time Approximation of Independent Set Parameterized by Treewidth.

[BibT_eX]

[DOI]

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

2022

Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver.

[BibT_eX]

[DOI]

Chien-Chung Huang

Pattara Sukprasert

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

2021

On Minimum Generalized Manhattan Connections.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures - 17th International Symposium, 2021

Coloring and Maximum Weight Independent Set of Rectangles.

[BibT_eX]

[DOI]

Bartosz Walczak

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Vertex Sparsification for Edge Connectivity.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

2020

From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More.

[BibT_eX]

[DOI]

SIAM J. Comput., 2020

On Finding Balanced Bicliques via Matchings.

[BibT_eX]

[DOI]

Wanchote Po Jiamjitrak

Ly Orgo

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2020

Multi-transversals for Triangles and the Tuza's Conjecture.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

New Binary Search Tree Bounds via Geometric Inversions.

[BibT_eX]

[DOI]

Wanchote Po Jiamjitrak

Proceedings of the 28th Annual European Symposium on Algorithms, 2020

Pinning down the Strong Wilber 1 Bound for Binary Search Trees.

[BibT_eX]

[DOI]

Julia Chuzhoy

Proceedings of the Approximation, 2020

2019

Mimicking Networks Parameterized by Connectivity.

[BibT_eX]

[DOI]

CoRR, 2019

New Tools and Connections for Exponential-Time Approximation.

[BibT_eX]

[DOI]

Algorithmica, 2019

A Tight Extremal Bound on the Lovász Cactus Number in Planar Graphs.

[BibT_eX]

[DOI]

Andreas Schmid

Sumedha Uniyal

Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

2018

Submodular unsplittable flow on trees.

[BibT_eX]

[DOI]

Math. Program., 2018

Multi-Finger Binary Search Trees.

[BibT_eX]

[DOI]

Proceedings of the 29th International Symposium on Algorithms and Computation, 2018

Survivable Network Design for Group Connectivity in Low-Treewidth Graphs.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2018

2017

Finding Triangles for Maximum Planar Subgraphs.

[BibT_eX]

[DOI]

Andreas Schmid

Proceedings of the WALCOM: Algorithms and Computation, 2017

Beyond Metric Embedding: Approximating Group Steiner Trees on Bounded Treewidth Graphs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More.

[BibT_eX]

[DOI]

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016

A Note on Fractional Coloring and the Integrality gap of LP for Maximum Weight Independent Set.

[BibT_eX]

[DOI]

Daniel Vaz

Electron. Notes Discret. Math., 2016

The landscape of bounds for binary search trees.

[BibT_eX]

[DOI]

CoRR, 2016

New Integrality Gap Results for the Firefighters Problem on Trees.

[BibT_eX]

[DOI]

Daniel Vaz

Proceedings of the Approximation and Online Algorithms - 14th International Workshop, 2016

2015

Two Lower Bounds for Shortest Double-Base Number System.

[BibT_eX]

[DOI]

Hiroshi Imai

Vorapong Suppakitpaisarn

IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 2015

A Global Geometric View of Splaying.

[BibT_eX]

[DOI]

CoRR, 2015

Greedy Is an Almost Optimal Deque.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures - 14th International Symposium, 2015

On Survivable Set Connectivity.

[BibT_eX]

[DOI]

Fabrizio Grandoni

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Social Network Monetization via Sponsored Viral Marketing.

[BibT_eX]

[DOI]

Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, 2015

Pattern-Avoiding Access in Binary Search Trees.

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Self-Adjusting Binary Search Trees: What Makes Them Tick?

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2015, 2015

How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking.

[BibT_eX]

[DOI]

Anna Adamaszek

Andreas Wiese

Proceedings of the Approximation, 2015

On Guillotine Cutting Sequences.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2015

2014

New Approximability Results for the Robust k-Median Problem.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory - SWAT 2014, 2014

Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31, 2014

Pre-reduction Graph Products: Hardnesses of Properly Learning DFAs and Approximating EDP on DAGs.

[BibT_eX]

[DOI]

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

Nearly Tight Approximability Results for Minimum Biclique Cover and Partition.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2014, 2014

2013

Graph Pricing Problem on Bounded Treewidth, Bounded Genus and k-Partite Graphs.

[BibT_eX]

[DOI]

Chic. J. Theor. Comput. Sci., 2013

Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Clustering With Center Constraints.

[BibT_eX]

[DOI]

Suresh Venkatasubramanian

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2013

Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses.

[BibT_eX]

[DOI]

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012

Multi-Attribute Profit-Maximizing Pricing (Extended Abstract)

[BibT_eX]

[DOI]

CoRR, 2012

Approximation algorithms and hardness of integral concurrent flow.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

Coloring and Maximum Independent Set of Rectangles.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing.

[BibT_eX]

[DOI]

Proceedings of the Internet and Network Economics - 6th International Workshop, 2010

Resource Minimization for Fire Containment.

[BibT_eX]

[DOI]

Julia Chuzhoy

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

2009

Stackelberg Pricing is Hard to Approximate within 2-ε

[BibT_eX]

[DOI]

CoRR, 2009

Maximum independent set of rectangles.

[BibT_eX]

[DOI]

Julia Chuzhoy

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

2005

Simple Distributed Algorithms for Approximating Minimum Steiner Trees.

[BibT_eX]

[DOI]

Jittat Fakcharoenphol

Proceedings of the Computing and Combinatorics, 11th Annual International Conference, 2005

2004

A deterministic near-linear time algorithm for finding minimum cuts in planar graphs.

[BibT_eX]

[DOI]

Jittat Fakcharoenphol