Source author record

Anak Yodpinyanee

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

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms Computational Complexity

Catalog footprint

Research overview

4works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Even $1 \times n$ Edge-Matching and Jigsaw Puzzles are Really Hard

We prove the computational intractability of rotating and placing $n$ square tiles into a $1 \times n$ array such that adjacent tiles are compatible--either equal edge colors, as in edge-matching puzzles, or matching tab/pocket shapes, as in jigsaw puzzles. Beyond basic NP-hardness, we prove that it is NP-hard even to approximately maximize the number of placed tiles (allowing blanks), while satisfying the compatibility constraint between nonblank tiles, within a factor of 0.9999999851. (On the other hand, there is an easy $1 \over 2$ -approximation.) This is the first (correct) proof of inapproximability for edge-matching and jigsaw puzzles. Along the way, we prove NP-hardness of distinguishing, for a directed graph on $n$ nodes, between having a Hamiltonian path (length $n-1$ ) and having at most $0.999999284 (n-1)$ edges that form a vertex-disjoint union of paths. We use this gap hardness and gap-preserving reductions to establish similar gap hardness for $1 \times n$ jigsaw and edge-matching puzzles.

preprint2016arXiv

Sublinear-Time Algorithms for Counting Star Subgraphs with Applications to Join Selectivity Estimation

We study the problem of estimating the value of sums of the form $S_p \triangleq \sum \binom{x_i}{p}$ when one has the ability to sample $x_i \geq 0$ with probability proportional to its magnitude. When $p=2$ , this problem is equivalent to estimating the selectivity of a self-join query in database systems when one can sample rows randomly. We also study the special case when $\{x_i\}$ is the degree sequence of a graph, which corresponds to counting the number of $p$ -stars in a graph when one has the ability to sample edges randomly. Our algorithm for a $(1 \pm \varepsilon)$ -multiplicative approximation of $S_p$ has query and time complexities $Ø(\frac{m \log \log n}{ε^2 S_p^{1/p}})$ . Here, $m=\sum x_i/2$ is the number of edges in the graph, or equivalently, half the number of records in the database table. Similarly, $n$ is the number of vertices in the graph and the number of unique values in the database table. We also provide tight lower bounds (up to polylogarithmic factors) in almost all cases, even when $\{x_i\}$ is a degree sequence and one is allowed to use the structure of the graph to try to get a better estimate. We are not aware of any prior lower bounds on the problem of join selectivity estimation. For the graph problem, prior work which assumed the ability to sample only \emph{vertices} uniformly gave algorithms with matching lower bounds [Gonen, Ron, and Shavitt. \textit{SIAM J. Comput.}, 25 (2011), pp. 1365-1411]. With the ability to sample edges randomly, we show that one can achieve faster algorithms for approximating the number of star subgraphs, bypassing the lower bounds in this prior work. For example, in the regime where $S_p\leq n$ , and $p=2$ , our upper bound is $\tilde{O}(n/S_p^{1/2})$ , in contrast to their $Ω(n/S_p^{1/3})$ lower bound when no random edge queries are available.

preprint2015arXiv

Dissection with the Fewest Pieces is Hard, Even to Approximate

We prove that it is NP-hard to dissect one simple orthogonal polygon into another using a given number of pieces, as is approximating the fewest pieces to within a factor of $1+1/1080-\varepsilon$ .

preprint2015arXiv

Local Computation Algorithms for Graphs of Non-Constant Degrees

In the model of \emph{local computation algorithms} (LCAs), we aim to compute the queried part of the output by examining only a small (sublinear) portion of the input. Many recently developed LCAs on graph problems achieve time and space complexities with very low dependence on $n$ , the number of vertices. Nonetheless, these complexities are generally at least exponential in $d$ , the upper bound on the degree of the input graph. Instead, we consider the case where parameter $d$ can be moderately dependent on $n$ , and aim for complexities with subexponential dependence on $d$ , while maintaining polylogarithmic dependence on $n$ . We present: a randomized LCA for computing maximal independent sets whose time and space complexities are quasi-polynomial in $d$ and polylogarithmic in $n$ ; for constant $ε> 0$ , a randomized LCA that provides a $(1-ε)$ -approximation to maximum matching whose time and space complexities are polynomial in $d$ and polylogarithmic in $n$ .

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.

Anak Yodpinyanee

Research overview

Is this your work?

4 publications

Even $1 \times n$ Edge-Matching and Jigsaw Puzzles are Really Hard

Sublinear-Time Algorithms for Counting Star Subgraphs with Applications to Join Selectivity Estimation

Dissection with the Fewest Pieces is Hard, Even to Approximate

Local Computation Algorithms for Graphs of Non-Constant Degrees

See the researcher in context

Building this map preview

Anak Yodpinyanee

Research overview

Is this your work?

4 publications

Even 1×n1 \times n1×n Edge-Matching and Jigsaw Puzzles are Really Hard

Sublinear-Time Algorithms for Counting Star Subgraphs with Applications to Join Selectivity Estimation

Dissection with the Fewest Pieces is Hard, Even to Approximate

Local Computation Algorithms for Graphs of Non-Constant Degrees

See the researcher in context

Building this map preview

Even $1 \times n$ Edge-Matching and Jigsaw Puzzles are Really Hard