graph theory

Proginoskes · science forum Guru Joined: 29 Apr 2005 Posts: 2593

Thomas Mautsch wrote:

Rich Holme · science forum beginner Joined: 06 Jun 2005 Posts: 45

dbd@gatekeeper.vic.com (David DeLaney) writes:

David DeLaney · science forum beginner Joined: 08 May 2005 Posts: 20

ks-robak <ks-robak@o2.pl> wrote:

BDH · science forum beginner Joined: 25 Oct 2005 Posts: 11

Exactly.

Proginoskes · science forum Guru Joined: 29 Apr 2005 Posts: 2593

Michael Harrington wrote:

Richard Reddy · science forum beginner Joined: 16 Nov 2005 Posts: 1

The statistics on child mortality for AIDS are fairly accurate, but the
"third world" depends on who you talk to. We have underdeveloped nations
in Africa, Asia and Latin America. Many developed nations also have
AIDS epidemics, including the USA. There is substantial margin for error in
the business of counting deaths for epidemics of all kinds. We also find
politics in official numbers, which are frequently wrong.

The issue of quality of life for people infected with AIDS is even
more tragic, given the high cost of drugs proven to be effective. The
poorest
nations are simply helpless in the face of this epidemic, lacking medical
infrastructure, public health education, or the ability to assist sick and
disabled people.

In my opinion, the age of AIDS victims is irrelevant. We should endeavor
to assist any nation or state unable to cope with this pandemic. It's the
human thing to do, whatever we think of particular statistics. The
suffering
is real and the AIDS epidemic is enormous. So too are millions of deaths
that might have been delayed by years or decades with appropriate medical
intervention.

I offer another challenge. Find a reputable organization and try to
be of help in some way. An organization can be in error with statistics,
but still be highly effective in delivering assistance, a process that
frequently
involves danger and hardship. There are many wonderful people stretched
out beyond reckoning in combating this global menace. You will find many
charities who hire "pros" to raise money, sometimes with questionable
tactics
or poor percentages reaching the intended recipients. By law, this
statistics
are public information.

Apathy is certainly a dangerous condition. I know little about this
organization,
but there are many putting their whole heart into the effort to fight this
epidemic.

If you want to hang your hat on some real statistical offenders, try the
antismoking crew. Prohibitionists love to exaggerate. For example, public
adds that say each cigarette shortens your life by 5 minutes.

<dsaklad@zurich.csail.mit.edu> wrote in message
news:1117871877.716280.18410@o13g2000cwo.googlegroups.com...

Matthew Roozee · science forum beginner Joined: 22 Oct 2005 Posts: 7

amanda.pascoe@gmail.com wrote:

Woeginger Gerhard · science forum beginner Joined: 30 Jul 2005 Posts: 5

unix68 <unix68@networld.at> wrote:
# Hi,
# I need help for solving the following problem (references to
# algorithms and papers).
#
# Given:
# P, p1,p2,...,pn all integers
# C, c1,c2,...,cn all integers
# P = constant
# C = constant
#
# Goal:
# maximize [P+sum(pj)]/[C+sum(cj)] for any j=1..n
#
# This means we have to find the optimal subset of elements
# out of a given set (1...n) such that the ratio
# [P+sum(pj)]/[C+sum(cj)] gets maximal.

In case all c1,...,cn are NON-NEGATIVE integers,
your problem is polynomially solvable. (There is
a direct solution via sorting, you do not even
need fractional programming.)

In case c1,...,cn are ARBITRARY integers,
your problem is NP-hard. (By a reduction from
subset sum.)

--Gerhard

___________________________________________________________
Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/

Guest

Well, yeah, actually a "trivial" lower bound can be derived easily.

Consider all k-sets of [1..n], we have totally

{n choose k} such sets.

and each coloring is going to color at most

(n/k)^k

of them. Therefore another lower bound should be

{n choose k}/(n/k)^k

with stirling's approximation, we can easily get a lower bound of

e^k, when n/k is large enough.

Nice day. Smile

Proginoskes · science forum Guru Joined: 29 Apr 2005 Posts: 2593

fhzhang@gmail.com wrote:

Guest

That's what I was thinking too. This problem seems well-defined and
should have been studied.

Write to you later.

Fenghui

Proginoskes · science forum Guru Joined: 29 Apr 2005 Posts: 2593

fhzh...@gmail.com wrote:

Guest

I tried some simple cases, your result seems correct.

I really appreciate your help. Nice weekend. Smile

Proginoskes · science forum Guru Joined: 29 Apr 2005 Posts: 2593

Binesh Bannerjee wrote:

Guest

Sorry I made a mistake,

ln(n/(k-1))/ln(k/(k-1))=(ln(n)-ln(k-1))/(ln(k)-ln(k-1))<ln(n)/ln(k)=log(n,k)

is not correct. But still when n=6,k=4, we have

ceil(ln(n/(k-1))/ln(k/(k-1)))=3

Three colorings are not enough do distinguish all 4-subsets of a 6-set.

Google