Source author record

C. J. Argue

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms math.CO math.MG

Catalog footprint

Research overview

4works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Lipschitz Selectors may not Yield Competitive Algorithms for Convex Body Chasing

The current best algorithms for convex body chasing problem in online algorithms use the notion of the Steiner point of a convex set. In particular, the algorithm which always moves to the Steiner point of the request set is $O(d)$ competitive for nested convex body chasing, and this is optimal among memoryless algorithms [Bubeck et al. 2020]. A memoryless algorithm coincides with the notion of a selector in functional analysis. The Steiner point is noted for being Lipschitz with respect to the Hausdorff metric, and for achieving the minimal Lipschitz constant possible. It is natural to ask whether every selector with this Lipschitz property yields a competitive algorithm for nested convex body chasing. We answer this question in the negative by exhibiting a selector which yields a non-competitive algorithm for nested convex body chasing but is Lipschitz with respect to Hausdorff distance. Furthermore, we show that being Lipschitz with respect to an $L_p$ -type analog to the Hausdorff distance is sufficient to guarantee competitiveness if and only if $p=1$ .

preprint2020arXiv

Chasing Convex Bodies with Linear Competitive Ratio

We study the problem of chasing convex bodies online: given a sequence of convex bodies $K_t\subseteq \mathbb{R}^d$ the algorithm must respond with points $x_t\in K_t$ in an online fashion (i.e., $x_t$ is chosen before $K_{t+1}$ is revealed). The objective is to minimize the sum of distances between successive points in this sequence. Bubeck et al. (STOC 2019) gave a $2^{O(d)}$ -competitive algorithm for this problem. We give an algorithm that is $O(\min(d, \sqrt{d \log T}))$ -competitive for any sequence of length $T$ .

preprint2020arXiv

Dimension-Free Bounds on Chasing Convex Functions

We consider the problem of chasing convex functions, where functions arrive over time. The player takes actions after seeing the function, and the goal is to achieve a small function cost for these actions, as well as a small cost for moving between actions. While the general problem requires a polynomial dependence on the dimension, we show how to get dimension-independent bounds for well-behaved functions. In particular, we consider the case where the convex functions are $κ$ -well-conditioned, and give an algorithm that achieves an $O(\sqrt κ)$ -competitiveness. Moreover, when the functions are supported on $k$ -dimensional affine subspaces--e.g., when the function are the indicators of some affine subspaces--we get $O(\min(k, \sqrt{k \log T}))$ -competitive algorithms for request sequences of length $T$ . We also show some lower bounds, that well-conditioned functions require $Ω(κ^{1/3})$ -competitiveness, and $k$ -dimensional functions require $Ω(\sqrt{k})$ -competitiveness.

preprint2015arXiv

Covers in Partitioned Intersecting Hypergraphs

Given an integer $r$ and a vector $\vec{a}=(a_1, \ldots ,a_p)$ of positive numbers with $\sum_{i \le p} a_i=r$ , an $r$ -uniform hypergraph $H$ is said to be $\vec{a}$ -partitioned if $V(H)=\bigcup_{i \le p}V_i$ , where the sets $V_i$ are disjoint, and $|e \cap V_i|=a_i$ for all $e \in H,~~i \le p$ . A $\vec{1}$ -partitioned hypergraph is said to be $r$ -partite. Let $t(\vec{a})$ be the maximum, over all intersecting $\vec{a}$ -partitioned hypergraphs $H$ , of the minimal size of a cover of $H$ . A famous conjecture of Ryser is that $t(\vec{1})\le r-1$ . Tuza conjectured that if $r>2$ then $t(\vec{a})=r$ for every two components vector $\vec{a}=(a,b)$ . We prove this conjecture whenever $a\neq b$ , and also for $\vec{a}=(2,2)$ and $\vec{a}=(4,4)$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.