Jake Wildstrom's Research
My publications:
- Wildstrom, D. Jacob. Cost thresholds for dynamic resource
location. Discrete Appl. Math. 156 (2008), no. 10,
1846–1855. (preprint, MR2432946, doi:10.1016/j.dam.2007.09.002)
- Wildstrom, D. Jacob. Resource relocation on asymmetric
networks. J. Graph Algorithms Appl. 14 (2010), no. 2,
149–163. (paper)
- Wildstrom, D. Jacob. Dynamic resource location with tropical algebra. Linear Algebra Appl. in press. (doi:10.1016/j.laa.2010.03.028)
I have a number of ongoing research projects. This is a partial
list of problems I'm currently engaged in. If you're interested in
learning more about any of
them, write to
me.
Realtime resource relocation
Service providers on communication, transportation, and any other
sort of network may relocate in response to changing conditions. For
instance, a mobile radio transmitter may be better served by moving
physically closer to its clients, or a software construct might
provide faster and less expensive service by being reinstalled on a
new system as its users' locations shift. A significant question is
when such relocations become expedient, given that there are costs
associated with both relocation and long-distance service.
The mathematical approach to this problem under consideration is
been to consider a finite set of possible client and server locations
and costs associated with both relocation and remote service. Then,
given an initial server location and a queue of client-requests to
serve, there is clearly a selection of relocations to minimize the
overall cost of providing service. This can be determined through
(highly inefficient) linear programming. Moving beyond the question of
perfect optimization with flawless knowledge of the entire request
sequence, two fundamental questions (which raise ancillary questions
with regard to network architecture and business practice) arise:
- Given imperfect future knowledge, i.e. only the next k
requests in an arbitrarily long sequence of requests, is it possible
to make a relocation decision which leads to optimal service
provision?
- When it is not possible to provide optimal service in the
situation described above, what is the ratio between the costs of
implementing a well-designed strategy based on limited information
and the costs of an omnisciently optimized strategy?
Useful References:
- F. R. K. Chung, R. L. Graham, and M. E. Saks. Dynamic search in
graphs. In Discrete algorithms and complexity (Kyoto, 1986),
volume 15 of Perspect. Comput., pages
351–387. Academic Press, Boston, MA, 1987.
- F. R. K. Chung, R. L. Graham, and M. E. Saks. A dynamic location problem for graphs. Combinatorica, 9(2):111–131, 1989.
- F. Chung and R. Graham. Dynamic location problems with limited
look-ahead. Theoret. Comput. Sci., 261(2):213–226,
2001. Computing and combinatorics (Taipei, 1998).
- R. Cuninghame-Green. Minimax algebra, volume 166
of Lecture Notes in Economics and Mathematical
Systems. Springer-Verlag, Berlin, 1979.
- E. Koutsoupias and C. H. Papadimitriou. On the k-server
conjecture. J. Assoc. Comput. Mach., 42(5):971–983,
1995.
Permutations of k-tuples with distinct sums
It was shown by Marshall Hall that, given an abelian group of order
$n$ and (not necessarily distinct)
elements a1,..., an thereof, there
is a permutation b1,..., bn of
elements of the group such that
each ai+bi is distinct if and only
if the ai add up to zero.
A question which is somewhat similar to this field of inquiry is as
follows: if we are given k
elements a1,..., ak
of Zn, are we guaranteed that there is a
permutation σ of 1,...,k so that the
sums ai+σi are all distinct
modulo n, and if so how many such σ are there? Such a
selection is clearly impossible if k>n. Hall's result
shows such a selection of σ is not necessarily possible
if k=n, but that it always is if k=n-1.
Kézdy and Snevily have conejctured that such a σ
always exists if k<n; and furthermore, that the
number of such σ is nonstrictly increasing in as a function
of n, and nonstrictily increasing as a function of k
for k<n.
Useful References:
- N. Alon, Additive Latin transversals. Israel J. Math. 117
(2000), 125–130.
- S. Dasgupta; G. Károlyi; O. Serra; B. Szegedy, Transversals of
additive Latin squares, Israel J. Math. 126 (2001),
17–28.
- M. Hall, A combinatorial problem on abelian
groups, Proc. Amer. Math. Soc. 3 (1952), 584–587.
- A. Kézdy and H. Snevily, Distinct Sums Modulo n
and Tree Embeddings, Combin. Probab. Comput. 11 (2002),
35–42.
- H. Snevily, The Cayley Addition Table
of Zn, Amer. Math Monthly 106
(1999), 584–585.
- Z. Sun, On Snevily's conjecture and restricted
sumsets, J. Combin. Theory, Ser. A 103 (2003),
291–304.
Return to aleph.
