Aditya Pillai

dblp:337/0020 · DBLP profile ↗
← Back
2ranked-venue papers
0as first author
2since 2021 · last 2023
0009-0006-2691-8313ORCID · corroborated

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 2 since 2021Databases, data management, data science and information retrieval · 1 · 1 since 2021
YearPublicationVenuePosition
2023 An Improved Approximation Algorithm for the Max-3-Section Problem
abstract
We consider the Max--Section problem, where we are given an undirected graph G=(V,E)equipped with non-negative edge weights w: E → R_+ and the goal is to find a partition of V into three equisized parts while maximizing the total weight of edges crossing between different parts. Max-3-Section is closely related to other well-studied graph partitioning problems, e.g., Max-Cut, Max-3-Cut, and Max-Bisection. We present a polynomial time algorithm achieving an approximation of 0.795, that improves upon the previous best known approximation of 0.673. The requirement of multiple parts that have equal sizes renders Max-3-Section much harder to cope with compared to, e.g., Max-Bisection. We show a new algorithm that combines the existing approach of Lassere hierarchy along with a random cut strategy that suffices to give our result.
Dor Katzelnick, Aditya Pillai, Roy Schwartz 0002, Mohit Singh
ESA2
2023 Analyzing Residual Random Greedy for monotone submodular maximization
Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Aditya Pillai
Inf. Process. Lett.4