|
|
| Author |
Message |
stonetiger
science forum beginner
Joined: 11 Feb 2005
Posts: 6
|
 Posted: Thu Mar 17, 2005 3:41 pm Post subject:
name of this minmax problem
|
|
|
x_i an integer, index i ranges from 1 to N
d_i a positive constant for each i from 1 to N
L a postive integer constant
Problem: Find the x_1,...,x_N that minimizes the maximum difference
abs(d_i*x_i-d_j*x_j) for any i and j in {1,...,N} and subject to
x_1+...+x_N=L.
Does anyone know if this problem have a common name and what it's
complexity is? |
|
| Back to top |
|
 |
stonetiger
science forum beginner
Joined: 11 Feb 2005
Posts: 6
|
| Posted: Thu Mar 17, 2005 7:54 pm Post subject:
Re: name of this minmax problem
|
|
|
Looked into it and (and at first glance) it seems that Hamilton's
method, Adam's method, et. al. are suboptimal algorithms. I didn't
have to look long to find an example where the solution from Hamilton's
method optimized neither my cost function or a L_p norm type one.
Maybe I should make sure I'm understanding things correctly before
making such claims, however. At least I know what the general problem
is called now. Thanks. |
|
| Back to top |
|
|
Chip Eastham
science forum Guru
Joined: 01 May 2005
Posts: 412
|
| Posted: Fri Mar 18, 2005 12:48 pm Post subject:
Re: name of this minmax problem
|
|
|
stonetiger wrote:
| Quote: | x_i an integer, index i ranges from 1 to N
d_i a positive constant for each i from 1 to N
L a postive integer constant
Problem: Find the x_1,...,x_N that minimizes the maximum difference
abs(d_i*x_i-d_j*x_j) for any i and j in {1,...,N} and subject to
x_1+...+x_N=L.
Does anyone know if this problem have a common name and what it's
complexity is?
|
Perhaps we could describe it as "simultaneous Diophantine
approximation"?
regards, chip |
|
| Back to top |
|
|
Brandon Moore
science forum beginner
Joined: 21 Mar 2005
Posts: 1
|
| Posted: Mon Mar 21, 2005 5:51 pm Post subject:
Re: name of this minmax problem
|
|
|
Woeginger Gerhard wrote:
| Quote: | I don't know what you mean by "sub-optimal".
|
.... that Hamilton's method produces a valid apportionment (i.e
x_1+...+x_N=L) that does not necessarily minimize the cost function
max_ij { abs(d_i*x_i-d_j*x_j) }. It does minimize some other cost
functions, but none that I'm interested in.
According to Balinski's book, the cost function I'm interested in was
addressed in an old paper "Apportionment of the U.S. House of
Representatives" by Burt & Harris. They use dynamic programming, but
their paper is a little short on the details.
I'm interested in the problem in relation to a discrete load balancing
setup, if it makes any difference. I just wanted an efficient way to
calculate the cost of the optimal solution so I could use it
numerically as a point of comparison. I think I'm on track now, so
thanks for the help.
Brandon |
|
| Back to top |
|
|
Proginoskes
science forum Guru
Joined: 29 Apr 2005
Posts: 2593
|
| Posted: Thu Apr 07, 2005 4:40 am Post subject:
Re: name of this minmax problem
|
|
|
stonetiger wrote:
| Quote: | x_i an integer, index i ranges from 1 to N
d_i a positive constant for each i from 1 to N
L a postive integer constant
Problem: Find the x_1,...,x_N that minimizes the maximum
difference abs(d_i*x_i-d_j*x_j) for any i and j in {1,...,N}
and subject to x_1+...+x_N=L.
Does anyone know if this problem have a common name and
what it's complexity is?
|
It's an integer program (like a linear program, but the variables have
to be integers). I can't say much more than that right off.
--- Christopher Heckman |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Thu Jan 08, 2009 5:03 pm | All times are GMT
|
|
Guitar Lessons | Free Credit Score | Loans | Mortgage Loans | Buy Anything On eBay
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
»
Combinatorics
