DIMACS Mixer Series - September 18, 1998
DIMACS Center, CoRE Building, Rutgers University, Busch Campus, Piscataway, NJ
Peter N. Yianilos, NEC
"Sequence Comparison in Theory and Practice"
We review three examples of recent theoretical work in the
general area of sequence comparison that also have an applied
component: i) Linear time quasi-convex bipartite matching and
its relationship to intelligent text retrieval, ii) learning
string edit distance costs and its application to
pronunciation modeling in speech recognition, and iii) inexact
context data compression and its application to DNA modeling.
for background information.
Ryan Martin, Rutgers University
The Shannon Capacity and Ramsey Theory
We will summarize some of the major results on the Shannon
Capacity and review some more recent results of Alon and Orlitsky.
We will show that the question of computing the Shannon capacity
for any graph is a Ramsey-like problem. We will use this view to
achieve some other results in the area of Shannon capacity.
Greg Perkins (paper in collaboration with Diane Souvaine),
"Efficient Radio Wave Front Propagation for Wireless Radio
As wireless network design and implementation is complicated,
wireless network engineers increasingly depend on wireless network
simulation engines. A signal-strength prediction system lies at
the foundation of every wireless simulator, making signal-strength
prediction for microcells and picocells an important research topic
in the radio field. Efficient and accurate methods are needed for
use in current wireless network design and future wireless network
This paper describes a system, PREDICT, designed for use in wireless
radio signal prediction research. PREDICT tracks the expansion of a
transmitter's wavefront by modeling the wavefront as an ever
expanding sphere centered upon the transmitter. The sphere's expansion
is tracked by discretizing the sphere's surface with a triangulation
and then propagating each triangular wavefront through the
environment. In the propagation prediction of these triangular wave
fronts, PREDICT supports reflection, transmission and diffraction based
upon the geometric optics (GO) model of electromagnetic waves. Signal
prediction is performed through summation of the predicted multi-path
components at a receiver.
PREDICT's algorithms have been specifically designed for use in radio
signal prediction. The current environments supported by PREDICT are
urban with flat or varied terrain and a single floor of a building,
where all obstacles in the environment have vertical or horizontal
walls. The system design is flexible, allowing PREDICT to be
expanded for use in many different environments. Modularity allows for
easy modification to the GO model or implementation of alternate radio
Gruia Calinescu, Rutgers University
"An Improved Approximation Algorithm for MULTIWAY CUT"
Given an undirected graph with edge costs and a subset of k nodes called
terminals, a multiway cut is a subset of edges whose removal disconnects
each terminal from the rest. MULTIWAY CUT is the Max SNP-Hard problem of
finding a multiway cut of minimum cost. Previously, a very simple
combinatorial algorithm due to Dahlhaus, Johnson, Papadimitriou, Seymour,
and Yannakakis gave a performance guarantee of 2(1-1/k).
In this talk, we present a new linear programming relaxation for MULTIWAY
CUT and an approximation algorithm based on it. The algorithm breaks the
threshold of 2 for approximating MULTIWAY CUT, achieving a performance
ratio of at most 1.5 - 1/k.
This is joint work with Howard Karloff and Yuval Rabani.
Victoria Ungureanu, Rutgers University
"A Mechanism for Establishing Policies for Electronic Commerce"
We introduce a mechanism for establishing policies for electronic
commerce in a unified and secure manner. A commercial policy can be
viewed as the embodiment of a contract between the principals
involved in a certain type of commercial activity, and it may be
concerned with such issues as: ensuring that a payment for services
is refunded under specified circumstances; preventing certificates
representing e-cash from being duplicated; ensuring that credit card
numbers are used only for the transaction they are intended for; and,
for certain socially sensitive transactions like the purchase of
drugs, ensuring auditability by proper authorities.
Our mechanism is based on a previously published concept of
law-governed interaction. It makes a strict separation between the
formal statement of a policy, which we call a ``law,'' and the
enforcement of this law, which is carried our by a set of
policy-independent trusted controllers. A new policy under this
scheme is created basically by formulating its law, and can be
easily deployed throughout a distributed system. This mechanism
enables a single agent to engage in several different activities,
subject to disparate policies.
Xin Guo, Rutgers University
"Is the market complete?: Towards a new model for the stick
A new model of an incomplete market allowing for stochastic
volatility is posed. The usual assumption that the stock price
is Markovian is modified by adjoining a hidden Markov process
to the Black-Scholes exponential Brownian motion model for
stock fluctuations. The drift and volatility parameters take
different values when the hidden Markov process is in different
states. For example, it is 0 when there is no subset of the market
which has or which believes it has, extra information, that is,
when the market is complete. However, the hidden process is in
state 1 when information is not equally shared by all, and then
the behavior of the members in the subset causes increased
fluctuations in the stock price.
Numerical simulation and discretization of the new model are
given. Corresponding optimal stopping times and option pricing
procedure are discussed.
Contacting the Center
Document last modified on September 4, 1998.