Abstract: For a number of optimization problems on randomgraphs
and hypergraphs, e.g., k-colorings, there is a very big gap between the
largest average degree for which known polynomial-time algorithms can
find solutions, and the largest average degree for which solutions provably
exist. We study this phenomenon by examining how sets of solutions
evolve as edges are added.We prove in a precise mathematical sense that,
for each problem studied, the barrier faced by algorithms corresponds
to a phase transition in the problems solution-space geometry. Roughly
speaking, at some problem-specific critical density, the set of solutions
shatters and goes from being a single giant ball to exponentially many,
well-separated, tiny pieces. All known polynomial-time algorithms work
in the ball regime, but stop as soon as the shattering occurs. Besides
giving a geometric view of the solution space of random instances our
results provide novel constructions of one-way functions.
Abstract: Motivated by the problem of efficiently collecting data from
wireless sensor networks via a mobile sink, we present an accelerated
random walk on RandomGeometricGraphs. Random
walks in wireless sensor networks can serve as fully local,
very simple strategies for sink motion that significantly
reduce energy dissipation but introduce higher latency in the
data collection process. While in most cases random walks
are studied on graphs like Gn,p and Grid, we define and experimentally
evaluate our newly proposed random walk on
the RandomGeometricGraphs model, that more accurately
abstracts spatial proximity in a wireless sensor network. We
call this new random walk the \~{a}-stretched random walk, and
compare it to two known random walks; its basic idea is
to favour visiting distant neighbours of the current node
towards reducing node overlap. We also define a new performance
metric called Proximity Cover Time which, along
with other metrics such as visit overlap statistics and proximity
variation, we use to evaluate the performance properties
and features of the various walks.
Abstract: Random scaled sector graphs were introduced as a generalization of randomgeometricgraphs to model networks of sensors using optical communication. In the random scaled sector graph model vertices are placed uniformly at random into the [0, 1]2 unit square. Each vertex i is assigned uniformly at random sector Si, of central angle {\'a}i, in a circle of radius ri (with vertex i as the origin). An arc is present from vertex i to any vertex j, if j falls in Si. In this work, we study the value of the chromatic number ボ\^O}(Gn), directed clique number {\`u}(Gn), and undirected clique number {\`u}2 (Gn) for random scaled sector graphs with n vertices, where each vertex spans a sector of {\'a} degrees with radius rn = ―~{a}ln n/n. We prove that for values {\'a} < ボ\^I}, as n → ∞ w.h.p., ボ\^O}(Gn) and {\`u}2 (Gn) are {\`E}(ln n/ln ln n), while {\`u}(Gn) is O(1), showing a clear difference with the randomgeometric graph model. For {\'a} > ボ\^I} w.h.p., ボ\^O}(Gn) and {\`u}2 (Gn) are {\`E} (ln n), being the same for random scaled sector and randomgeometricgraphs, while {\`u}(Gn) is {\`E}(ln n/ln ln n).
Abstract: Motivated by the problem of efficient sensor network data collection via a mobile sink, we present undergoing research in accelerated random walks on RandomGeometricGraphs. We first propose a new type of random walk, called the {\'a}-stretched random walk, and compare it to three known random walks. We also define a novel performance metric called Proximity Cover Time which, along with other metrics such us visit overlap statistics and proximity variation, we use to evaluate the performance properties and features of the various walks. Finally, we present future plans on investigating a relevant combinatorial property of RandomGeometricGraphs that may lead to new, faster random walks and metrics.
