Transcript Integrated Logistics PROBE

Integrated Logistics PROBE
Princeton University, 10/31-11/1
Presentation Outline
 Defining
Logistics
 Applications and Key Problems
 Facility Location
 Known
Results
 Open Problems
 Hierarchical
 Known
Network Design
Results
 Open Problems
Defining Logistics
 Given
service demands, must satisfy
 “transporting products” from A to B
 Goal is to minimize service cost
 Aggregation problems
Facility Location Problems

Open facilities
 Each demand near
to some facility
 Minimize sum or
max distances
 Some restriction on
facilities to open
 NP Hard (1.46)
Hierarchical Aggregation

More than one level
of “cluster”
 Basically building a
tree or forest
 Solve FL over and
over… but don’t
want to pay much!
App: Trucking Service
App: Trucking Service
 Talk
by Ted Gifford
 Schneider
Logistics
 Multi-Billion
dollar industry
 Solve FL problems
 Difficult
to determine costs, constraints
 Often solve problems exactly (IP)
 Usually ~500-1000 nodes
Open Problems: Trucking
 Often
multi-commodity FL
 Hierarchical, but typically only 3-4 levels
 Need extremely accurate solutions
 “average
case” bounds?
App: Databases
App: Databases
 Talk
 U.
by Sudipto Guha
Penn, AT&T research
 Distributed
databases
 Determining
 Database
 Many
data placement on network
Clustering
models, measures
 Many different heuristics!
Open Problems: Databases
 Databases
can be VERY large
 “polynomial-time”
not good enough
 Streaming/sampling based approaches
 Data
may change with time
 Need
 No
fast “update” algorithm
clear measure of quality
 “quick
and dirty” may be best
App: Genetics
App: Genetics
 Talk
by Kamesh Munagala
 Stanford
 Finding
University, Strand Genomics
patterns in DNA/proteins
 Known
DNA code, but proteins mysterious
 Can scan protein content of cells fast
 Scan is not very accurate though
 Find patterns in healthy vs. tumor cells
Open Problems: Genetics
 Huge
amounts of data!
 Also,
 Try
not very accurate, many “mistakes”
to find separating dimension
 Potentially
 Really
 Find
many clusterings, find “best”
two-step problem
best “dimension” of exp. combinations
 Cluster it, see if it separates
Results: Facility Location
 Talk
by David Shmoys
 Cornell
University
 Three
main
paradigms
 Linear
Program
Rounding
 Primal-Dual Method
 Local Search
Results: Facility Location
 Talk
by Kamal Jain
 Microsoft
 Talk
Research
by Mohammad Mahdian
 MIT
 Best
approximation: 1.52
based “greedy” algorithm
 Solve LP to find “worst-case” approx
 Primal-dual
Results: Facility Location
 Talk
by Martin Pal
 Cornell
University
 Problem
of FL with hard capacities
 O(1) via local search
 Open: O(1) via primal-dual or LP?
 What
is LP gap?
 Often good to have “lower bound”
Results: Facility Location
 Talk
by Ramgopal Mettu
 Dartmouth
 FAST
University
approximations for k-median
 O(nk)
constant approx
 Repeated sampling approach
 Compared
 Slightly
to DB clustering heuristics
slower, much more accurate
Open Problems: FL
 Eliminate
the gap!
 1.52
vs. 1.46, VERY close
 Analysis of Mahdian is tight
 Maybe time to revisit lower bound?
 K-Median
 Local
 Load
Problem
search gives 3, improve?
Balanced Problem
 Exact
on the lower bounds?
Results: Network Design

Talk by Adam Meyerson


CMU
O(log n) for single-sink
 O(log n log log n) for
one function
 O(1) for one sink, one
function
Results: Network Design
 Talk
by Kunal Talwar
 UC
Berkeley
 Improved
 LP
O(1) for one sink, function
rounding
Results: Network Design
 Connected
 Talks

by Anupam Gupta
Lucent Research, CMU
 Chaitanya

Facility Location
Swamy
Cornell University
 Give
9-approx for the problem
 Greedy,
primal-dual approaches
Results: Network Design
 Talk
by Amitabh Sinha
 CMU
 Combining
 O(log
 O(1)
Buy-at-bulk with FL
n) immediate, but what about O(1)?
for one cable type, small constant
 O(1) in general
 What about capacitated? K-med?
Open Problems: ND
 Multi-commodity,
 No
 O(1)
 LP
 O(1)
multiple function
nontrivial approximations known!
for single sink?
gap not even known!
for single function?
 Cannot
 Make
depend on tree embedding
the constants reasonable!
 Euclidean problem: easier?
Conclusions
 Many
applications and open problems!
 Must get in touch with DB community…
 Workshop was a success, but…
 Need
more OR participation
 Too short notice for faculty?
 Plan
another workshop, late March
 Hope
to have some more solutions!
Thanks to Princeton
Local Arrangements by Moses Charikar + Mitra Kelly