>>> Complexity Seminar のお知らせ <<<

 　日時：６月２９日（土）、２時〜３時半頃
 　場所：東京工業大学 南３号館 電気情報系会議室              

 　題目：Optimal Information Gathering on the Internet       
     　  with Time and Cost Constraints                      

 　発表：Tao Jiang
  　     Computer Science Department
   　    McMaster University
    　   Hamilton, Ontario, Canada

　 概要：

The World Wide Web provides access to vast amounts of information, 
but with increasing frequency content providers are charging 
for the information and services they supply.  Thus the consumer 
must weigh the benefit of asking for information against the cost
(both in terms of money and time) of acquiring it.
We study information gathering strategies that maximize the 
expected value to the consumer.  In our model there is a 
single information request, which has a known {¥em benefit} to
the consumer.   To satisfy the request, {¥em queries} can be sent
simultaneously or in sequence to any one of a finite set of independent
{¥em information sources}. For each source we know the monetary cost
of making the query, the amount of time it will take, and the
probability that the source will be able to provide the requested
information. A {¥em policy} specifies which sources to contact at
which times, and the {¥em expected value} of the policy can be defined
as some function of the likelihood that the policy will yield an answer
and the expected monetary cost and time delay associated with executing
the policy. The problem is to find an expected-value-maximizing policy.

In this lecture, we explore several variants of the objective value
function. The problem of devising an optimal policy is shown to be
NP-hard for all the variants, and some efficient approximation
algorithms and schemes with guaranteed error bounds are presented.
A fundamental difference between our problem and the traditional
scheduling problems is that, while a traditional schedule has to
execute {¥em all} its jobs, a querying policy terminates whenever one
successful answer is returned.

This is a joint work with Oren Eztioni, Steve Hanks and Omid Madani.