DIMACS Mixer Series - September 18, 1998

DIMACS Center, CoRE Building, Rutgers University, Busch Campus, Piscataway, NJ

1.

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.
			
See:	
http://www.neci.nj.nec.com/homepages/pny/papers/quasi/main.html
	                                       /sed/main.html
	                                       /cdna/main.html
for background information.


2.

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.


3.

Greg Perkins (paper in collaboration with Diane Souvaine),
Rutgers University 

"Efficient Radio Wave Front Propagation for Wireless Radio
Signal Prediction"

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 
research.

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
modeling methods.


4.

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.


5.

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.

6.

Xin Guo, Rutgers University

"Is the market complete?: Towards a new model for the stick
market"

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. 

  

Other Workshops

DIMACS Homepage