Author name cluster

Thomas W. Pensyl

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

SODA Conference 2023 Conference Paper

Improved Bi-point Rounding Algorithms and a Golden Barrier for k -Median

Kishen N. Gowda
Thomas W. Pensyl
Aravind Srinivasan
Khoa Trinh

The current best approximation algorithms for k -median rely on first obtaining a structured fractional solution known as a bi-point solution, and then rounding it to an integer solution. We improve this second step by unifying and refining previous approaches. We describe a hierarchy of increasingly-complex partitioning schemes for the facilities, along with corresponding sets of algorithms and factor-revealing non-linear programs. We prove that the third layer of this hierarchy is a 2. 613-approximation, improving upon the current best ratio of 2. 675, while no layer can be proved better than 2. 588 under the proposed analysis. On the negative side, we give a family of bi-point solutions which cannot be approximated better than the square root of the golden ratio, even if allowed to open k + o ( k ) facilities. This gives a barrier to current approaches for obtaining an approximation better than. Altogether we reduce the approximation gap of bi-point solutions by two thirds.

Details

SODA Conference 2015 Conference Paper

An Improved Approximation for k -median, and Positive Correlation in Budgeted Optimization

Jaroslaw Byrka
Thomas W. Pensyl
Bartosz Rybicki
Aravind Srinivasan
Khoa Trinh

Dependent rounding is a useful technique for optimization problems with hard budget constraints. This framework naturally leads to negative correlation properties. However, what if an application naturally calls for dependent rounding on the one hand, and desires positive correlation on the other? More generally, we develop algorithms that guarantee the known properties of dependent rounding, but also have nearly best-possible behavior – near-independence, which generalizes positive correlation – on “small” subsets of the variables. The recent breakthrough of Li & Svensson for the classical k -median problem has to handle positive correlation in certain dependent-rounding settings, and does so implicitly. We improve upon Li-Svensson's approximation ratio for k -median from 2. 732 + ε to 2. 611 + ε by developing an algorithm that improves upon various aspects of their work. Our dependent-rounding approach helps us improve the dependence of the runtime on the parameter ε from Li-Svensson's N O (1 /ε 2 ) to N O ((1/ε) log (1/ε)). (An erratum has been attached to the previously published proceedings.).

Details