Abstract:
Methods and apparatuses are provided that employ an improved greedy algorithm for addressing NP-Hard problems and others like them. The improved greedy algorithm considers possible local savings while also remaining significantly fast.

Description:
TECHNICAL FIELD  
         [0001]    This invention relates to computers and software, and more particularly to methods and apparatuses for providing computer-based techniques providing greedy approaches for facility location, resource allocation, and/or other like problems/decisions.  
         BACKGROUND OF THE INVENTION  
         [0002]    Numerous classical and contemporary problems are integer optimization problems that are intractable. Such problems are commonly referred to as NP-Hard problems and often addressed with heuristics that provide a solution, but not always information on the solution&#39;s quality. An approximation algorithms&#39; framework, on the other hand, usually provides a guarantee on the quality of the solution obtained. Various frameworks have been used to develop computer-based algorithms in specific problem areas with increasingly improved performance.  
           [0003]    One example of an NP-Hard problem is the classical problem of facility location. The facility location problem is essentially the problem of determining were to locate facilities such that the intended users or clients of the facilities are properly served and costs are reduced or minimized. Here, for example, the facility may include a fire station, a retail store, a factory, a ware house, an office complex, or other like buildings/structures. Another example is a resource allocation problem associated with providing access and/or services to clients in a substantially efficient manner. In the context of the information age, the resource allocation problem may arise in determining where to locate computer/communication resources such as servers, routers, switches, hubs, networks, antennas, and the like.  
           [0004]    These and other like problems are typically considered NP-Hard problems, because it is widely believed that one cannot find the optimal solution (e.g., a minimal cost solution, minimal access time solution, etc.) within a reasonable amount of time. One reason for this assumption is that there are usually several or possibly too many variables/options to consider or otherwise accurately account for.  
           [0005]    There is a continuing need, therefore, for improved algorithms and related methods and apparatuses for addressing such problems and others like them.  
         SUMMARY OF THE INVENTION  
         [0006]    Improved algorithms and related methods and apparatuses are provided for addressing NP-Hard such problems and others like them. Examples of such problems include, but are not limited to, facility location problems and resource allocation problems. Those skilled in the art will recognize that there are many other problems that can essentially be framed as a facility location or a resource allocation problem.  
           [0007]    In accordance with certain aspects of the present invention, a significantly fast algorithm is provided that approximately solves such problems. The algorithm can be computer-based or otherwise implemented through some form of logic. As used herein, the term logic refers to any form or combined forms of logic, for example, hardware, firmware and/or software logic.  
           [0008]    In accordance with certain exemplary implementations of the present invention, the approximation guarantee of the algorithm can be as low as about 1.61. This means that the solution obtained is guaranteed to be at lost only 61 percent worse then the optimal solution. This is only a pessimistic guarantee, for typical examples, the algorithm usually performs within a few percentage points of the optimal solution.  
           [0009]    The above stated needs and others are met, for example, by a method for use in a computing or other like device. The method includes identifying a plurality of potential “resources” and a plurality of “users”. For each of the users, an access parameter is also identified for each of the potential resources.  
           [0010]    The method then enters and iterative process beginning with, for each of the potential resources, establishing a plurality of user groups and determining a corresponding group access parameter. For example, the group access parameter may be the average access cost for users in the group to access the resource. Next the method includes selecting one of the group parameters. This may include selecting the lowest average group access parameter, for example, out of all of those determined. The corresponding potential resource for the selected (picked) group parameter is then re-identified as a candidate resource and each user in the corresponding user group is then assigned to the candidate resource, provided that the user has not already been assigned to another candidate resource. If and once a plurality candidate resources have been identified, then for each user assigned to one of the candidate resources, the method consider whether to re-assign the user to a different candidate resource based at least on a comparison of access parameters associated with the user and each of the candidate resources. In certain implementations, the re-assignment of users provides for a local savings. The method then iterates back to the beginning until each of the users has been assigned to a corresponding candidate resource.  
           [0011]    In this example and others herein, potential resources include any physical item or a service that is suitable for being accessed in some manner by at least one of the users. By way of example and not limitation, a potential resource may include a facility, a building, a platform, a business location, a store, an office, a warehouse, a factory, a medical facility, a port, a service capability, a computing resource, a server, a communication resource, an antenna, a satellite, an information repository, a database, a public utility resource, a natural resource, a crop, a supply, a transportation resource, an education resource, an entertainment resource, and the like.  
           [0012]    As for applicable users, anyone or anything suitable for accessing at least one of the potential resources may be considered a user in this example. Hence, users may include one person, a group of people, a business, a consumer, a client, geographically-related resource users, a city, an entity, an organization, a student, a patient, a subscriber, an animal, a computing device, a computer program, a communication device, a receiver, a transmitter, a transportation device, and the like. These examples are not intended to limit the scope of the term “user”.  
           [0013]    This exemplary method may also include identifying a minimal candidate resource threshold or other like value/test. After completing the iteration and assigning users to resources, the method would then, determine if each of the candidate resources satisfies the minimal candidate resource threshold, e.g., based on the number of the users assigned to the candidate resource. If the candidate resource does not satisfy the minimal candidate resource threshold, then for each the user assigned to the candidate resource, the method would re-assign the user to another one of the candidate resources based at least on the access parameters associated with the user. When this happens and all of the users are re-assigned, then the losing candidate resource is re-identified as one of the potential resources.  
           [0014]    Once the candidate resources have been settled upon, then method would then include outputting the results, for example, to a data storage device or other computer-readable media, a display screen, a printer, a network, etc. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0015]    A more complete understanding of the various methods and apparatuses of the present invention may be had by reference to the following detailed description when taken in conjunction with the accompanying drawings wherein:  
         [0016]    [0016]FIG. 1 is a block diagram depicting an exemplary computer system suitable for use performing the novel algorithm in logic, in accordance with certain exemplary implementations of the present invention.  
         [0017]    [0017]FIG. 2 is a block diagram illustratively depicting a plurality of possible facilities or resources, a plurality of clients that the algorithm assigns or otherwise associates each with at least one of the facilities/resources, and “costs” for the client to access or otherwise use a facility/resource represented by the exemplary interconnecting arrows, in accordance with certain exemplary implementations of the present invention.  
         [0018]    [0018]FIG. 3 is a flow diagram depicting a method for a facility/resource algorithm that can be implemented in logic, in accordance with certain exemplary implementations of the present invention.  
         [0019]    [0019]FIG. 4 is an illustrative graph depicting results of an optimization method, in accordance with certain exemplary implementations of the present invention.  
     
    
     DETAILED DESCRIPTION  
       [0020]    Description Overview  
         [0021]    This description is arranged to present the reader with an exemplary computing environment that may be used for processing data according to the techniques and/or exemplary algorithms described herein. Following that, the techniques are described in sufficient mathematical detail to allow those skilled in the art to apply such techniques to various problems using a computer or like device. An exemplary method based on the mathematical techniques, is then presented for use within logic such as that available in the exemplary computing environment.  
         [0022]    Exemplary Computing Environment  
         [0023]    [0023]FIG. 1 illustrates an example of a suitable computing environment  120  on which the subsequently described methods and arrangements may be implemented.  
         [0024]    Exemplary computing environment  120  is only one example of a suitable computing environment and is not intended to suggest any limitation as to the scope of use or functionality of the improved methods and arrangements described herein. Neither should computing environment  120  be interpreted as having any dependency or requirement relating to any one or combination of components illustrated in computing environment  120 .  
         [0025]    The improved methods and arrangements herein are operational with numerous other general purpose or special purpose computing system environments or configurations.  
         [0026]    As shown in FIG. 1, computing environment  120  includes a general-purpose computing device in the form of a computer  130 . The components of computer  130  may include one or more processors or processing units  132 , a system memory  134 , and a bus  136  that couples various system components including system memory  134  to processor  132 .  
         [0027]    Bus  136  represents one or more of any of several types of bus structures, including a memory bus or memory controller, a peripheral bus, an accelerated graphics port, and a processor or local bus using any of a variety of bus architectures. By way of example, and not limitation, such architectures include Industry Standard Architecture (ISA) bus, Micro Channel Architecture (MCA) Ibus, Enhanced ISA (EISA) bus, Video Electronics Standards Association (VESA) local bus, and Peripheral Component Interconnects (PCI) bus also known as Mezzanine bus.  
         [0028]    Computer  130  typically includes a variety of computer readable media. Such media may be any available media that is accessible by computer  130 , and it includes both volatile and non-volatile media, removable and non-removable media.  
         [0029]    In FIG. 1, system memory  134  includes computer readable media in the form of volatile memory, such as random access memory (RAM)  140 , and/or non-volatile memory, such as read only memory (ROM)  138 . A basic input/output system (BIOS)  142 , containing the basic routines that help to transfer information between elements within computer  130 , such as during start-up, is stored in ROM  138 . RAM  140  typically contains data and/or program modules that are immediately accessible to and/or presently being operated on by processor  132 .  
         [0030]    Computer  130  may further include other removable/non-removable, volatile/non-volatile computer storage media. For example, FIG. 1 illustrates a hard disk drive  144  for reading from and writing to a non-removable, non-volatile magnetic media (not shown and typically called a “hard drive”), a magnetic disk drive  146  for reading from and writing to a removable, non-volatile magnetic disk  148  (e.g., a “floppy disk”), and an optical disk drive  150  for reading from or writing to a removable, non-volatile optical disk  152  such as a CD-ROM, CD-R, CD-RW, DVD-ROM, DVD-RAM or other optical media. Hard disk drive  144 , magnetic disk drive  146  and optical disk drive  150  are each connected to bus  136  by one or more interfaces  154 .  
         [0031]    The drives and associated computer-readable media provide nonvolatile storage of computer readable instructions, data structures, program modules, and other data for computer  130 . Although the exemplary environment described herein employs a hard disk, a removable magnetic disk  148  and a removable optical disk  152 , it should be appreciated by those skilled in the art that other types of computer readable media which can store data that is accessible by a computer, such as magnetic cassettes, flash memory cards, digital video disks, random access memories (RAMs), read only memories (ROM), and the like, may also be used in the exemplary operating environment.  
         [0032]    A number of program modules may be stored on the hard disk, magnetic disk  148 , optical disk  152 , ROM  138 , or RAM  140 , including, e.g., an operating system  158 , one or more application programs  160 , other program modules  162 , and program data  164 .  
         [0033]    The improved methods and arrangements described herein may be implemented within operating system  158 , one or more application programs  160 , other program modules  162 , and/or program data  164 .  
         [0034]    A user may provide commands and information into computer  130  through input devices such as keyboard  166  and pointing device  168  (such as a “mouse”). Other input devices (not shown) may include a microphone, joystick, game pad, satellite dish, serial port, scanner, camera, etc. These and other input devices are connected to the processing unit  132  through a user input interface  170  that is coupled to bus  136 , but may be connected by other interface and bus structures, such as a parallel port, game port, or a universal serial bus (USB).  
         [0035]    A monitor  172  or other type of display device is also connected to bus  136  via an interface, such as a video adapter  174 . In addition to monitor  172 , personal computers typically include other peripheral output devices (not shown), such as speakers and printers, which may be connected through output peripheral interface  175 .  
         [0036]    Computer  130  may operate in a networked environment using logical connections to one or more remote computers, such as a remote computer  182 . Remote computer  182  may include many or all of the elements and features described herein relative to computer  130 .  
         [0037]    Logical connections shown in FIG. 1 are a local area network (LAN)  177  and a general wide area network (WAN)  179 . Such networking environments are commonplace in offices, enterprise-wide computer networks, intranets, and the Internet.  
         [0038]    When used in a LAN networking environment, computer  130  is connected to LAN  177  via network interface or adapter  186 . When used in a WAN networking environment, the computer typically includes a modem  178  or other means for establishing communications over WAN  179 . Modem  178 , which may be internal or external, may be connected to system bus  136  via the user input interface  170  or other appropriate mechanism.  
         [0039]    Depicted in FIG. 1, is a specific implementation of a WAN via the Internet. Here, computer  130  employs modem  178  to establish communications with at least one remote computer  182  via the Internet  180 .  
         [0040]    In a networked environment, program modules depicted relative to computer  130 , or portions thereof, may be stored in a remote memory storage device. Thus, e.g., as depicted in FIG. 1, remote application programs  189  may reside on a memory device of remote computer  182 . It will be appreciated that the network connections shown and described are exemplary and other means of establishing a communications link between the computers may be used.  
         [0041]    Improved Algorithm Overview  
         [0042]    A simple and natural greedy algorithm is presented herein for the metric uncapacitated facility location problem achieving an approximation guarantee of 1.61 whereas the best previously known was 1.73. The greedy algorithm has a property which allows one to apply the technique of Lagrangian relaxation. Using this property, for example, one can find even better approximation algorithms for many variants of the facility location problem, such as the capacitated facility location problem with soft capacities, a common generalization of the k-median and facility location problem, and others. Also provided is a lower bound on the approximation of the k-median problem.  
         [0043]    Introduction  
         [0044]    In the following exemplary (uncapacitated) facility location problem, assume that one has a set F of n f  facilities and a set C of n c  cities. For every facility iεF, a nonnegative number f i  is given as the opening cost of facility i. Furthermore, for every city jεC and facility iεF, there is a connection cost (e.g., access cost, service cost, etc.) c ij  between city j and facility i.  
         [0045]    The objective is to open a subset of the facilities in F, and connect each city to an open facility so that the total cost is substantially minimized. This exemplary mathematical description considers the metric version of this problem, i.e., the connection costs satisfy the triangle inequality.  
         [0046]    Such problems have many applications in operations research, and recently in the network design problems such as placement of routers and caches, agglomeration of traffic or data, and web server replications in a content distribution network (CDN), for example. In the last decade the problem was studied extensively from the perspective of approximation algorithms.  
         [0047]    Different approaches such as LP rounding, primal-dual method, local search, and combinations of these methods with cost scaling and greedy post-processing are used to solve the facility location problem and its variants. Until now, the best known approximation algorithm for this problem achieved a factor of 1.728. To achieve this factor, the conventional algorithm essentially combined the ideas of cost scaling, greedy augmentations, and a primal-dual algorithm of to marginally improve a (1+2/e) approximation algorithm based on LP-rounding techniques. One potential drawback of this type of conventional algorithm is that it needs to solve large linear programs and therefore has a long processing running time/requirement. Using about the same ideas, others have presented an O( n   3 ) algorithm with approximation ratio 1.853. In has been shown that a simple greedy algorithm achieves an approximation ratio of 1.861 in O(n 2  log n) time. For the case of sparse graph, still others have provided faster (3+o(1))-approximation algorithms. Regarding hardness results, it is believed that it is likely impossible to get an approximation guarantee of 1.463 for the metric facility location problem, unless NP ⊂ DTIME[n O(loglog n) ].  
         [0048]    Here, in the description, simple and natural heuristic algorithms/techniques are provided for the facility location problem and others like it, achieving an approximation factor of 1.61 with the running time O( n   3 ).  
         [0049]    The exemplary algorithm is an improvement on conventional greedy algorithms. The technique used for the analysis of this algorithm is to express different constraints that are imposed by the problem statement or by the algorithm as linear inequalities, so that one gets a bound on the approximation ratio (or in the exemplary case, the exact approximation ratio) of the algorithm by solving a particular series of linear programs, which are referred to herein as factor-revealing LP. This scheme has some similarity to the idea of the LP bound in coding theory (e.g., LP bound gives the best known bounds on the minimum distance of a code with a given rate by bounding the solution of a linear program that contains various linear constraints, mainly MacWilliams identities). In the context of approximation algorithms, the idea of LP bound has been used for computing the approximation algorithm of an algorithm for the minimum latency problem. This conventional technique enables one to compute the approximation ratio of the algorithm empirically, and provides a straightforward way to prove a bound on the approximation ratio. In the case of the novel algorithm presented herein, this technique also enables one to compute the tradeoff between the approximation ratio of facility costs versus the approximation ratio of the connection costs. The exemplary mathematical algorithm, its analysis, and a discussion about this tradeoff are presented in the following sections.  
         [0050]    Among all previously known facility location algorithms, the primal-dual algorithm is perhaps the most versatile one in that it can be used to obtain algorithms for other variants of the problem, such as k-median, a common generalization of k-median and facility location, capacitated facility location with soft capacities, prize collecting facility location, and facility location with outliers. This versatility is partly because of the simplicity of that algorithm, and partly (in the case of k-median, common generalization of k-median and facility location, and capacitated facility location) because of a property of the algorithm which allows one to apply the Lagrangian relaxation technique.  
         [0051]    The novel mathematical algorithm presented herein has a property, which will be referred to as the Lagrangian multiplier preserving property, with an approximation factor that represents an increase over the primal-dual algorithm. This enables one to obtain algorithms for some variants of the facility location problem. In particular, in this description an algorithm is presented that solves a common generalization of the facility location problem and k-median within a factor of 4. In this exemplary problem, which is referred to herein as the k-facility location problem, an instance of the facility location problem and an integer k are given and the objective is to find a substantially cheap/low-cost solution that opens at most k facilities.  
         [0052]    The k-median problem is a special case of this problem in which all opening costs are 0. The k-median problem has been studied extensively and the best known approximation algorithm for this problem to date achieves a factor of 3+ε. The k-facility location problem has also been studied in operations research, and the best previously known approximation factor for this problem was 6.  
         [0053]    The Lagrangian multiplier preserving property of the novel algorithm presented herein enables one to produce a 3-approximation algorithm for a capacitated version of the facility location problem, in which one is allowed to open more than one facility at any location. This problem may be referred to as the capacitated facility location problem with soft capacities. The best previously known approximation algorithm for this problem has a factor of 3.46, and is based on a facility location algorithm together with the observation that any α-approximation algorithm for the uncapacitated facility location problem yields an algorithm with an approximation ratio of 2α for the capacitated facility location problem with soft capacities.  
         [0054]    As mentioned, in this description some lower bounds are also proven. Here, for example, it is shown that the k-median problem cannot be approximated within a factor strictly less than 1+2/e, unless NP ⊂ DTIME[n O(loglog n) ]. This is an improvement over the conventionally known lower bound of 1+1/e. Note that this result shows that k-median is a strictly harder problem to approximate than the facility location problem. As will be seen, a lower bound is the best tradeoff one can hope to achieve between the approximation factors for the facility cost and the connection cost in the facility location problem.  
         [0055]    Exemplary Algorithm for the Metric Facility Location Problem  
         [0056]    As is known, the facility location problem may be captured by commonly known integer programs. For the sake of convenience, in this description another equivalent formulation for the problem is provided.  
         [0057]    Thus, let us say that a star consists of one facility and several cities. The cost of a star is the sum of the opening cost of the facility and the connection costs between the facility and all the cities in the star.  
         [0058]    Let S be the set of all stars. The facility location problem can be thought of as picking a minimum cost set of stars such that each city is in at least one star. This problem can be captured by the following integer program. In this program, x S  is an indicator variable denoting whether star S is picked and c S  denotes the cost of star S.  
               Thus   ,     
        minimize          
            ∑     S   ∈   S              c   S          x   S              
          subject                 to                   ∀     j   ∈       C        :                       ∑       S        :        j     ∈   S            x   S         ≥   1                
          ∀     S   ∈     S        :          x   S       ∈     {     0   ,   1     }                 (   1   )                               
 
         [0059]    The LP-relaxation of this program is:  
             minimize        
            ∑     S   ∈   S              c   S          x   S              
          subject                 to                   ∀     j   ∈       C        :                       ∑       S        :        j     ∈   S            x   S         ≥   1                
          ∀     S   ∈       S        :                     x   S       ≥   0                 (   2   )                               
 
         [0060]    The dual program is:  
             maximize        
            ∑     j   ∈            C                   α   j              
          subject                 to                   ∀     S   ∈       S        :                       ∑     j   ∈     S   ⋂              C                   α   j           ≤     c   S                  
          ∀     j   ∈       C        :                     α   j       ≥   0                 (   3   )                               
 
         [0061]    One may think of the variable α j  in the dual program as the share of city j of the total expenses. It is clear from LP-duality that if an algorithm finds a solution for the facility location problem of cost T, and values α j  for jεC such that  
         [0062]    Σ jεC α j =T  
         [0063]    and for every star S,  
         [0064]    Σ jεS∩C α j ≦γc S    
         [0065]    for some fixed number γ≧1, then the approximation ratio of the algorithm is at most γ.  
         [0066]    Another way of looking at this is to consider an optimal solution for an instance of the problem. For every facility i that is opened in this solution and the collection A of cities that are connected to it, one may write the inequality Σ jεA α j ≦γ(f i +Σ jεA C ij ). By adding up these inequalities, one will find out that the cost of the solution presented herein is at most γ times the cost of the optimal solution. This fact is the basis of the analysis presented herein.  
         [0067]    This method, which is called dual fitting, can be considered a primal-dual type method. The only difference is that in primal-dual algorithms one usually relaxes the complementary slackness conditions to obtain a solution for the primal and a solution for the dual so-that the ratio of the values of the objective functions for these two solutions is bounded by the approximation factor of the algorithm. However, in the dual fitting scheme here one may relax the inequalities in the dual program. Therefore, the following exemplary algorithm finds a solution for the primal, and an infeasible solution for the dual with the some value for the objective function. The amount by which the dual inequalities are relaxed (or in other words, the amount by which one must shrink the dual solution so that it fits the dual) will give a bound on the approximation factor of the algorithm. This fact is one basis of the analysis herein.  
         [0068]    An Exemplary Algorithm  
         [0069]    In this section a notion of time is introduced into the algorithm. The algorithm starts at time 0. At this time, all cities are unconnected, all facilities are closed, and the budget of every city j, denoted by B j , is initialized to 0.  
         [0070]    Act 1: At every moment, each city j offers some money from its budget to each closed facility i. The amount of this offer is computed as follows: If j is unconnected, the offer is equal to max(B j −c ij , 0) (i.e., if the budget of j is more than the cost that it has to pay to get connected to i, it offers to pay this extra budget to i); If j is already connected to some other facility i′, then its offer to facility i is equal to max(c i j −c ij , 0) (i.e., the amount that j offers to pay to i is equal to the money that it would save if it switches its facility from i′ to i).  
         [0071]    Act 2: While there is an unconnected city, increase the time, and simultaneously, increase the budget of each unconnected city at the same rate (i.e., every unconnected city j has B j =t at time t), until one of the following events occur (if multiple events occur at the same time, process them in an arbitrary order):  
         [0072]    a. For some closed facility i, the total offer that it receives from cities is equal to the cost of opening i. In this case, open facility i, and for every city j (connected or unconnected) which has a non-zero offer to i, connect j to i. The amount that j had offered to i is now called the contribution of j toward i, and j is no longer allowed to decrease this contribution.  
         [0073]    b. For some unconnected city j, and some facility i that is already open, the budget of j is equal to the connection cost between j and i. In this case, connect city j to facility i. The contribution of j toward i is zero.  
         [0074]    Act 3: For every city j, set α j  (the share of j of the total expenses) equal to the budget of j at the end of algorithm. Notice that this value is also equal to the time that j first gets connected.  
         [0075]    Notice also that once a city gets connected, one stops increasing its budget. Also, the budget of each connected city is always equal to the connection cost that it pays at the time, plus the total contribution that it has given to the facilities.  
         [0076]    At any time during the execution of this exemplary algorithm, the budget of each connected city is equal to its current connection cost plus its total contribution towards open facilities.  
         [0077]    Based on the above description of the exemplary algorithm, it can be seen that:  
         [0078]    LEMMA 1. The total cost of the solution found by the above algorithm is equal to the sum of α j &#39;s.  
         [0079]    In order to prove an approximation guarantee of γ, it is enough to show that for every star S, the sum of α j &#39;s of the cities in S is at most γ times the cost of S. In order to compute such a γ), an optimization program can be defined (e.g., called the factor-revealing LP) whose solution gives the value of γ. In the subsequent section a factor-revealing LP is used to prove an upper bound of 1.61 on the approximation ratio of the exemplary algorithm above.  
         [0080]    The above exemplary algorithm is similar to conventional greedy algorithms, however, rather that having cities stop offering money to facilities as soon as they get connected to a facility, the exemplary algorithm allows cities to still offer some money (e.g., “savings”—the amount that they could save by switching their facility) to other facilities. As a result, the exemplary algorithm finds a solution that cannot be improved just by opening new facilities, and therefore it cannot be improved by conventional greedy augmentation procedures as may other known algorithms.  
         [0081]    Deriving an Exemplary Factor-Revealing LP  
         [0082]    Various constraints can be expressed that are imposed by the problem or by the structure of the algorithm as inequalities, so that one can determine a bound on the value of γ defined above by solving a series of linear programs.  
         [0083]    Consider a star S consisting of a facility of opening cost f (with a slight misuse of the notation, one may call this facility f), and k cities numbered 1 through k. Let d j  denote the connection cost between facility f and city j, and α j  denote the share of j of the expenses, as defined in the above exemplary algorithm. One may assume without loss of generality that  
         α 1 ≦α 2 ≦ . . . ≦α k .  (4)  
         [0084]    However, one needs more variables to capture the execution of the exemplary algorithm. For every i (1≦i≦k), consider the situation of the algorithm at time t=α i −ε, where ε is very small, i.e., just a moment before city gets connected for the first time. At this time, each of the cities 1, 2, . . . , i−1 might be connected to a facility. For every j&lt;i, if city j is connected to some facility at time t, let r j,i  denote the connection cost between this facility and city j; otherwise, let r j,i :=α j . Obviously, the latter case occurs only if α i =α j . It turns out that these variables (f, d j &#39;s, α j &#39;s, and r j,i &#39;s) are enough to determine some inequalities to bound the ratio of the sum of α j &#39;s to the cost of S (i.e., f+Σ j=1   k d j ).  
         [0085]    First, notice that once a city gets connected to a facility, its budget remains the same and it cannot take back its contribution to a facility, so it can never get connected to another facility with a higher connection cost. This implies that for every j,  
           r   j,j+1   ≧r   j,j+2   ≧ . . . ≧r   j,k .  (5)  
         [0086]    Now, consider the time t=α i −ε. At this time, the amount of offer of city j toward facility f is equal to:  
         [0087]    max(r j,i −d j , 0) if j&lt;i, and  
         [0088]    max(t−d j , 0) if j≧i.  
         [0089]    Notice that this holds even if j&lt;i and α i =α j . It is clear from the exemplary algorithm that the total offer of cities to a facility can never become larger than the opening cost of the facility. Thus, there is the following inequality:  
                   ∑     j   =   1       i   -   1            max        (         r     j   ,   i       -     d   j       ,   0     )         +       ∑     j   =   i     k          max        (         α   i     -     d   j       ,   0     )           ≤     f   .             (   6   )                               
 
         [0090]    Another important constraint to use is the triangle inequality. By the triangle inequality and the definition of r j,i , for every j&lt;i, the connection cost between city i and the facility to which city j is connected at time t=α i −ε (let&#39;s call this facility f′) is at most r j,i +d i +d j . This cost cannot be less than t, since if it is, the exemplary algorithm could have connected the city i to the facility f′ at a time earlier than t, which is a contradiction. Here, one needs to be careful with the special case α i =α j . In this case, R j,i +d i +d j  is not more than t. If α i ·α j , the facility f′ is open at time t and therefore city i can get connected to it, if it can pay the connection cost. This argument shows that for every 1≦j&lt;i≦k,  
         α i   &lt;r   j,i   +d   i   +d   j .  (7)  
         [0091]    The above inequalities form the following optimization program, which is referred to as the factor-revealing LP.  
         [0092]    Notice that although the following optimization program is not written in the form of a linear program, one skilled in the art can easily change it to a linear program by introducing new variables and inequalities.  
               maximize                       ∑     i   =   1     k          α   i         f   +       ∑     i   =   1     k          d   i                  
          subject                 to                    ∀     1   ≤   i   &lt;     k        :                     α   i       ≤     α     i   +   1                
          ∀     1   ≤   j   &lt;   i   &lt;     k        :                     r     j   ,   i         ≥     r     j   ,     i   +   1                  
          ∀     1   ≤   j   &lt;   i   ≤     k        :                     α   i       ≤       r     j   ,   i       +     d   i     +     d   j                
          ∀     1   ≤   i   ≤       k        :                      ∑       j   =   1       i   -   1                       max        (         r     j   ,   i       -     d   j       ,   0     )           +       ∑     j   =   1     k          max        (         α   i     -     d   j       ,   0     )           ≤   f            
            ∀     1   ≤   j   ≤   i   ≤     k        :                     α   j           ,     d   j     ,   f   ,       r     j   ,   i       ≥   0               (   8   )                               
 
         [0093]    LEMMA 2: If z k  denotes the solution of the factor-revealing LP, then for every star S consisting of a facility and k cities, the sum of α j &#39;s of the cities in S in the exemplary algorithm is at most z k c S .  
         [0094]    Proof. Inequalities 4, 5, 6, and 7 derived above imply that the values α j ,d j ,f,r j,i  from the exemplary algorithm constitute a feasible solution of the factor-revealing LP. Thus, the value of the objective function for this solution is at most z k . □ 
         [0095]    LEMMA 1 and LEMMA 2 further imply the following:  
         [0096]    LEMMA 3: Let z k  be the solution of the factor-revealing LP, and γ:=sup k {z k }. Then the exemplary algorithm solves the metric facility location problem with an approximation factor of γ.  
         [0097]    Solving the Factor-Revealing LP  
         [0098]    As mentioned above, the optimization program (8) can be written as a linear program. This enables one to use an LP-solver to solve the factor-revealing LP for small values of k, in order to compute the numerical value of γ. Table 1 below shows a summary of results that are obtained by solving the factor-revealing LP using CPLEX. It appears based on experimental results that z k  is an increasing sequence that converges to some number close to 1.6 and hence γ≈1.6.  
                                           TABLE 1                           Solution of the factor-revealing LP                k   max i≦k z i                              10   1.54147           20   1.57084           50   1.58839           100   1.59425           200   1.59721           300   1.59819           400   1.59868           500   1.59898                      
 
         [0099]    By solving the factor-revealing LP for any particular value of k, one gets a lower bound on the value of γ. In order to prove an upper bound on γ, one needs to present a general solution to the dual of the factor-revealing LP. Unfortunately, this is not an easy task in general. For example, performing a tight asymptotic analysis of the LP bound is still an open question in coding theory. However, here empirical results can help. Thus, one may solve the dual of the factor-revealing LP for small values of k to get an idea as to the general optimal solution. Using this, it is usually possible (although sometimes tedious) to prove a close-to-optimal upper bound on the value of z k . This technique has been used to prove an upper bound of 1.61 on γ.  
         [0100]    One may use the optimal solution of the factor-LP to construct an example on which the exemplary algorithm performs at least z k  times worse than the optimum. Such results imply the following:  
         [0101]    THEOREM 4: The exemplary algorithm herein solves the facility location problem in time O(n 3 ), where n=max(n f ,n c ). Its approximation ratio is equal to the supremum of the solution of the maximization program (8), which is less than 1.61, and more than 1.598.  
         [0102]    The Tradeoff Between Facility and Connection Costs  
         [0103]    One may define the cost of a solution in the facility location problem as the sum of the facility cost (i.e., total cost of opening facilities) and the connection cost. With the exemplary algorithm above, one can achieve an overall performance guarantee of 1.61. However, sometimes it is useful to get different approximation guarantees for facility and connection costs. The following theorem gives such a guarantee. The proof is similar to the proof of Lemma 3.  
         [0104]    THEOREM 5: Let γ f ≧1 and γ c :=sup k {z k }, where z k  is the solution of the following optimization program:  
               maximize                         ∑     i   =   1     k          α   i       -       γ   f        f           ∑     i   =   1     k          d   i                
          subject                 to                    ∀     1   ≤   i   &lt;     k        :                     α   i       ≤     α     i   +   1                
          ∀     1   ≤   j   &lt;   i   &lt;     k        :           r     j   ,   i         ≥     r     j   ,     i   +   1                  
          ∀     1   ≤   j   &lt;   i   ≤     k        :                     α   i       ≤       r     j   ,   i       +     d   i     +     d   j                
          ∀     1   ≤   i   ≤       k        :             ∑     j   =   1       i   -   1                       max        (         r     j   ,   i       -     d   j       ,   0     )           +       ∑     j   =   1     k          max        (         α   i     -     d   j       ,   0     )           ≤   f            
            ∀     1   ≤   j   ≤   i   ≤     k        :                     α   j           ,     d   j     ,   f   ,       r     j   ,   i       ≥   0               (   9   )                               
 
         [0105]    Then for every instance I of the facility location problem, and for every solution SOL for 1 with facility cost F SOL  and connection cost C SOL , the cost of the solution found by Algorithm 1 is at most γ f F SOL +γ c C SOL .  
         [0106]    A solution has been computed using the optimization program (9) for k=100, and several values of γ f  between 1 and 3, to get an estimate of the corresponding γ c &#39;s. Exemplary results are illustrated in the line graph  400  of FIG. 4. Every point (γ f ,γ′ c ) on line  402  in this diagram represents a value of γ f , and the corresponding estimate for the value of  γ   c . Line  404  shows a lower bound that holds unless NP ⊂ DTIME[n O(loglog n) ] and is proved in subsequent sections.  
         [0107]    An important advantage here is that all the inequalities ALG≦γ f F SOL +γ c C SOL  are satisfied by a single algorithm. As described in the next section, the case γ f =1 can be of particular theoretical interest for designing other algorithms.  
         [0108]    Variants of the Problem  
         [0109]    The k-median problem differs from the facility location problem in at least two respects: (1) there is no cost for opening facilities, and (2) there is an upper bound k, that is supplied as part of the input, on the number of facilities that can be opened. The k-facility location problem is a common generalization of k-median and the facility location problem. In this problem there is an upper bound k in the number of facilities that can be opened, as well as costs for opening facilities.  
         [0110]    The k-medium problem can be reduced to the facility location problem in the following sense: suppose A is an approximation algorithm for the facility  11  location problem. Consider an instance I of the problem with optimum cost OPT, and let F and C be the facility and connection costs of the solution found by A. Algorithm A is called a Lagrangian Multiplier Preserving α-approximation (or LMP α-approximation for short) if for every instance I, C≦α(OPT−F). It can be shown that an LMP α-approximation algorithm for the metric facility location problem gives rise to a 2α-approximation algorithm for the metric k-median problem. This theorem also holds for a common generalization of the metric k-facility location problem.  
         [0111]    Hence,  
         [0112]    LEMMA 6: An LMP α-approximation algorithm for the facility location problem gives a 2α-approximation algorithm for the k-facility problem.  
         [0113]    Here, an LMP 2-approximation algorithm is provided for the metric facility location problem based on the exemplary algorithm described earlier. This will result in a 4-approximation algorithm for the metric k-facility location problem whereas the best previously known was a 6-approximation.  
         [0114]    In the capacitated facility location problem, for every facility there is one more parameter, which indicates the capacity of the facility, i.e., the number of cities it can serve. This version of the problem in which one is allowed to open each facility more than once is referred to herein as the capacitated facility location problem with soft capacities.  
         [0115]    Conventional techniques for facility location algorithms have shown a 4-approximation capability for the metric capacity facility location problem with soft capabilities. One can generalize such results to the following lemma. This lemma, together with the LMP 2-approximation facility location algorithm gives a 3-approximation algorithm for the metric capacitated facility location problem with soft capabilities.  
         [0116]    LEMMA 7: An LMP α-approximation algorithm for the metric uncapacitated facility location problem leads to an (α+1)-approximation algorithm for the metric capacitated facility location problem with soft capabilities.  
         [0117]    One can now show that there is an LMP 2-approximation algorithm for the metric facility location problem. The proof is based on Theorem 5 together with known scaling techniques. One can prove the following lemma using this technique.  
         [0118]    LEMMA 8: Assume there is an algorithm A for the metric facility location problem that for every instance I and every solution. SOL for I, A finds a solution of cost at most F SOL +αC SOL , where F SOL  and C SOL  are facility and connection costs of SOL, and a is a fixed number. Then there is an LMP α-approximation algorithm for the metric facility location problem.  
         [0119]    For proof, consider the following algorithm: The algorithm constructs another instance I′ of the problem by multiplying the facility opening costs by a, runs the exemplary algorithm (presented earlier) on this modified instance I′, and outputs its answer. Suppose αF (F with the original costs) and C be the facility and the connection costs in the solution provided by this run. Then αF+C≦α(F SOL +C SOL ), which implies that this algorithm is an LMP α-approximation.  
         [0120]    Now one only needs to prove the following:  
         [0121]    THEOREM 9: For every instance I and every solution SOL for I, Algorithm 1 finds a solution of cost at most F SOL +2C SOL , where F SOL  and C SOL  are facility and connection costs of SOL.  
         [0122]    Proof: By Theorem 5 one needs only to prove that the solution of the factor-revealing LP (9) with γ f =1 is at most 2. To do so, one may write the maximization program (9) as the following equivalent linear program:  
                 maximize                     ∑     i   =   1     k          α   i         -   f          
          subject                 to          
              ∑     i   =   1     k          d   i       =   1                    ∀     1   ≤   i   &lt;       k        :                     α   i       -     α     i   +   1         ≤   0            
          ∀     1   ≤   j   &lt;   i   &lt;       k        :                     r     j   ,     i   +   1           -     r     j   ,   i         ≤   0                       ∀     1   ≤   j   &lt;   i   ≤       k        :                     α   i       -     r     j   ,   i       -     d   i     -     d   j       ≤   0            
          ∀     1   ≤   j   &lt;   i   ≤       k        :                     r     j   ,   i         -     d   i     -     g     i   ,   j         ≤   0            
          ∀     1   ≤   i   ≤   j   ≤       k        :                     α   i       -     d   j     -     h     i   ,   j         ≤   0            
          ∀     1   ≤   i   ≤       k        :                       ∑     j   =   1       i   -   1                       g     i   ,   j           +       ∑     j   =   i     k          h     i   ,   j         -   f     ≤   0            
          ∀   i     ,     j        :                     α   j       ,     d   j     ,   f   ,     r     j   ,   i       ,     g     i   ,   j       ,       h     i   ,   j       ≥   0             (   10   )                               
 
         [0123]    One then needs to prove an upper bound of 2 on the solution of the above LP. Since this program is a maximum program, it is enough to prove the upper bound for any relaxation of the above program. Numerical results (for a fixed value of k, e.g., k=100) suggest that removing the second, third, and seventh inequalities of the above program does not remove the solution. Therefore, one may relax the above program by removing these inequalities. Now, it is a simple exercise to write down the dual of the relaxed linear program and compute its optimal solution. This solution corresponds to multiplying the third, fourth, fifth, and sixth inequalities of the linear program (10) by I/k, and the first inequality by (2−1/k) and adding up these inequalities. This produces an upper bound of 2 −1 /k on the value of the objective function. Thus, if γ f =1, then γ c ≦2. In fact, γ c  is precisely equal to 2, as shown by the following solution for the program (9):  
               α   i     =     {           2   -     1   /   k             i   =   1             2         2   ≤   i   ≤   k                           d   i     =     {         1         i   =   1             0         2   ≤   i   ≤   k                           r     j   ,   i       =     {         1         j   =   1             2         2   ≤   j   ≤   k                         f   =     2        (     k   -   1     )                                   
 
         [0124]    This example illustrates that the above analysis of the factor-revealing LP is tight.  
         [0125]    Lemma 8 and Theorem 9 provide an LMP 2-approximation algorithm for the metric facility location problem. Those skilled in the art will recognize that this result not only improves on previous results but also provides fairly straightforward algorithms that are adaptable/applicable to various other problems.  
         [0126]    Lower Bounds  
         [0127]    This section explores some impossibility results. The first result is the following theorem, which together with Feige&#39;s result on the hardness of set-cover shows that there is no  
       (     1   +     2   e     -   ɛ     )                         
 
         [0128]    -approximation algorithm for k-median unless NP c DTIME[n O(loglog n) ]. The proof is similar to the one used by Guha and Khuller to prove the hardness of the metric facility location problem (see, e.g., S. Guha and S. Khuller, “Greedy Strikes Back: Improved Facility Location Algorithms”, published in the Journal of Algorithms, 31:228-248, 1999).  
         [0129]    THEOREM 10: The metric k-median problem cannot be approximated within a factor strictly smaller than 1+2/e unless minimum set-cover can be approximated within a factor of cln n for c&lt;1.  
         [0130]    Theorem 10 improves a lower bound of 1+1/e. Notice that Theorem 10 proves that k-median is a strictly harder problem to approximate than the facility location problem because the latter can be approximated within a factor of 1.61.  
         [0131]    THEOREM 11: Let γ f  and γ c  be constants with γ c &lt;1+2e −γ     f   . Assume there is an algorithm A that for every instance I of the metric facility location problem, A finds a solution whose cost is not more than γ f F SOL +γ c C SOL  for every solution SOL for 1 with facility and connection costs F SOL  and C SOL . Then minimum set-cover can be approximated within a factor of cln n for c&lt;1.  
         [0132]    Line  404  in FIG. 4 shows the lower bound provided by the above theorem. The above theorem shows that finding an LMP  
         (     1   +     2   e     -   ɛ     )          -        approximation                         
 
         [0133]    for the metric facility location problem is hard. Also, known integrality gap examples show that Lemma 6 is tight. This shows that one cannot use Lemma 6 as a black box to obtain a smaller factor than  
       2   +     4   e                           
 
         [0134]    for the k-median problem. Note that a 3+ε approximation is already known for the problem. Hence if one wants to improve this factor using the Lagrangian relaxation technique then it will be necessary to look into the underlying LMP algorithm as already been done, for example, by Charikar and Guha (see, e.g., M. Charikar and S. Guha, “Improved Combinatorial Algorithms For Facility Location and k-Median Problems”, published in  Proceedings of the  40 th    Annual IEEE Symposium on Foundations of Computer Science,  378-388, October 1999).  
         [0135]    The Factor-Revealing LP Technique  
         [0136]    This section further elaborates on the techniques of using factor-revealing LPs used to analyze the algorithms presented herein. This section demonstrates this technique by applying it in combination with dual fitting to a classical greedy algorithm for the set cover problem. This section also explains how one can use computers to predict and prove bounds on the solution to the factor-revealing LP.  
         [0137]    A re-statement of the greedy algorithm for the set cover problem is as follows. All uncovered elements raise their dual-variables until a new set S goes tight (e.g., its cost equals the sum of the values of the dual variables of its elements). At this point, the set S is picked. Newly covered elements pay for the cost of S with their dual values. In doing so, they withdraw their contributions offered towards the cost of any other set. This ensures that at the end of the algorithm the total contribution of the elements is equal to the sum of the cost of the picked sets. However, one might not get a feasible dual solution. To make the dual solution feasible, one may look for the lowest positive number Z, so that when the dual solution is shrunk by a factor of Z, it becomes feasible. An upper bound on the approximation factor of the algorithm is obtained by maximizing Z over all possible instances. This known technique is referred to as dual fitting. With this in mind, focus will now be placed on the factor-revealing LP technique which is used to estimate the value of Z.  
         [0138]    Clearly Z is also the maximum factor by which any set is over-tight.  
         [0139]    Consider any set S. One can determine the worst factor, over all sets and over all possible instances of the problem, by which a set S is over-tight. Let the elements in S be 1, 2, . . . , k. Let x i  be the dual variable corresponding to the element i at the end of the algorithm. Without loss of generality we may assume that x 1 ≦x 2 ≦ . . . ≦x k . It is easy to see that at time t=x i   − , total duals offered to S is at least (k−i+1)x i . Therefore, this value cannot be greater than the cost of the set S (denoted by c S ). The optimum solution of the following mathematical program gives an upper bound on the value of Z (note that c S  is a variable not a constant):  
         [0140]    maximize  
                 ∑     i   =   1     k                     x   i         c   s             (   11   )                               
 
         [0141]    subject to  
         [0142]    ∀1≦i&lt;k: x i ≦x i+1    
         [0143]    ∀1≦i≦k: (k−i+1)x i ≦c s    
         [0144]    ∀1≦i≦k: x i ≧0  
         [0145]    c s ≧1  
         [0146]    The above optimization program can be turned into a linear program by adding the constraint c S =1 and changing the objective function to Σ i=1   k x i . The linear program is essentially a “factor-revealing LP”. Notice that the factor-revealing LP has nothing to do with the LP formulation of the set cover problem; it is only used in order to analyze this particular algorithm. This is an important distinction between the factor-revealing LP technique, and other LP-based techniques in approximation algorithms.  
         [0147]    Once one formulates the analysis of the algorithm as a factor-revealing LP, then one can use computers to empirically compute the upper bound given by the factor-revealing LP on the approximation ratio of the algorithm. This is very useful, since if the empirical results suggest that the factor-revealing LP does not produce a good approximation ratio, then one may try adding other inequalities to the factor-revealing LP. For this one might introduce new variables to capture the execution of the algorithm more accurately. For example, in an earlier section above, variables r j,i  were introduced to get a good bound on the approximation ratio of the algorithm.  
         [0148]    The next step is to analyze the factor-revealing LP and derive an upper bound on the value of its solution. For the set cover example above, this step is fairly trivial since the factor-revealing LP associated with the algorithm is quite simple. However, in general this can be a difficult step of the proof. Here, for example, one can employ computers to get ideas about the proof, as explained below. Proving Theorem 4 would have been very difficult without using these techniques.  
         [0149]    Since the factor-revealing LP provides an upper bound on the approximation ratio of the algorithm, one can relax some of the constraints of the LP to make it simpler. After each relaxation, one can use computers to verify that this relaxation does not change the value of the objective function drastically. After simplifying the factor-revealing LP in this way, one can find an upper bound on its solution by finding a feasible solution for its dual for every k. Again, here one can use a computer to solve the dual linear program for a couple hundred values of k, to observe, for example, a trend in the values of the optimal dual solution. After guessing a sequence of dual solutions, one has to theoretically verify their feasibility. For complicated linear programs, additional parameters may be included to help guess a general dual solution in terms of these parameters and optimize over the choice of these parameters at the end.  
         [0150]    Note that in general this technique does not guarantee the tightness of the analysis, because sometimes the algorithm performs well not because of local structures but for some global reason(s). Sill, in many cases one may get a tight example from a feasibly solution of the factor-revealing LP. For example, from any feasible solution of the factor-revealing LP (11), one can construct the following instance: There are k elements 1, . . . , k, a set S={1, . . . , k} of cost 1+ε which is the optima solution, and sets S i ={i} of cost x i  for i=1, . . . , k. It is easy to verify that the algorithm works Σx i  times worse than the optimal in this instance. This means that the approximation ratio of the set cover algorithm is precisely equal to the solution of the factor-revealing LP, which is H n .  
         [0151]    Graphical Depiction of Facilities/Resources and Clients  
         [0152]    Given the teachings of the exemplary mathematical techniques and algorithms in the previous sections, attention is now drawn to FIG. 2, which is a block diagram illustratively depicting a setting  200  having a plurality of possible facilities/resources  202 , a plurality of clients  204  that the algorithm assigns or otherwise associates each with at least one of the facilities/resources  202 , and “costs” for the client to access or otherwise use a facility/resource represented by the exemplary interconnecting arrows  208 , in accordance with certain exemplary implementations of the present invention.  
         [0153]    As shown, client  204   a  in this example is able to access or otherwise use facility/resources  202   a  with a “cost” of  206   a , facility/resources  202   b  with a “cost” of  206   b , and facility/resources  202   c  with a “cost” of  206   c . Client  204   b  is able to access or otherwise use facility/resources  202   a  with a “cost” of  208   a , facility/resources  202   b  with a “cost” of  208   b , and facility/resources  202   c  with a “cost” of  208   c.    
         [0154]    The term “cost” is used in this section to represent at least one parameter associated with the effort, expense, time, distance, etc., that is required of the client  204  to properly access or otherwise use a possible facility/resource as intended.  
         [0155]    In FIG. 2, for example, when considering a facility location problem each facility  202   a - n  represents a potential suitable location for a facility. By way of example, facility  202   a - n  may represent potential locations to build new retail grocery stores within a city. The clients  204   a - m  in this example could represent retail shoppers that live in and around the city. The costs (e.g.,  206   a - c ,  208   a - c ) in this example may represent the travel time for the respective client  204  to access each respective facility  202 . The facility location problem in this example would be to determine which facility or facilities to build to adequately serve the clients. Ideally, the resulting facility building expenses would be minimized or otherwise kept low, while also providing a “cost” efficient solution for the intended clients. The algorithm provided herein tends to select facilities that tend to provide the lowest average costs.  
         [0156]    In another example, when considering a resource allocation problem, such as, data servers, each resource  202   a - n  represents a potential suitable point/location for a data server. By way of example, resources  202   a - n  may represent potential points/nodes/locations to build new data servers within one or more networks. Clients  204   a - m  in this second example could represent other computers/devices that access the network resources including the data servers. The costs (e.g.,  206   a - c ,  208   a - c ) in this second example may represent the communication effort for the respective client  204  to access each respective resource  202 . The resource allocation problem in this example would be to determine which resources should be established to adequately serve the clients. Ideally, the resulting resource expenses would be minimized or otherwise kept low, while also providing a “cost” efficient solution for the intended clients. The exemplary algorithm described herein tends to select resources that provide the lowest average costs. Note that the term “client” used in this example in a more generic sense and as such is not meant to limit the other computers/devices to actual client devices as often used in client-server relationships.  
         [0157]    An Exemplary Flow-Diagram  
         [0158]    With the graphical representation of FIG. 2 in mind and also considering the previously described algorithm features, attention is drawn next to FIG. 3, which is a flow diagram depicting a method  300  for a facility/resource algorithm that can be implemented in logic, in accordance with certain exemplary implementations of the present invention.  
         [0159]    In act  302  information about the facilities/resources, clients, and/or costs are processed, entered, estimated, etc., in preparation for the other acts in method  300 .  
         [0160]    Note that method  300  represents an iterative process, so a counting variable X is use in this example to help illustrate some of the iteration. Other iteration techniques may be employed. In act  304 , X is set to X+1 and the X th  facility/resource is selected for consideration.  
         [0161]    In act  306 , the clients are placed in order based on cost for the selected X th  facility/resource. In act  308 , the average cost for the selected X th  facility/resource is determined for “client groups”. Client groups include one or more clients. Thus, for example, one client group would include the first client (as ordered in act  306 ), another client group would include the first and second clients (again, as ordered in act  306 ), and yet another client group would include first, second and third clients (also as ordered in act  306 ). This exemplary client grouping technique basically adds the next client in the order to the next client group, and a plurality of client groups are considered, with the last client group including all of the clients. In act  310  the average costs for the selected X th  facility/resource is stored.  
         [0162]    In act  312 , if all of the facilities to be considered have been considered, then method  300  continues to act  314 , otherwise method  300  iterates back to act  304  and the next facility/resource (X+1) is considered via acts  304 - 312 .  
         [0163]    In act  314 , a facility/resource is “picked” based on the stored cost information from step  310 , e.g., the lowest average cost client group. This picked facility/resource is associated with the client(s) in the applicable client group such that the facility/resource is a candidate for building and the applicable clients are assigned to it.  
         [0164]    Assuming that this is the first picked facility/resource, then method  300  continues with act  318 , wherein it is determined if all of the clients have been assigned to a facility/resource. If there are still some clients that have yet to be assigned to a facility/resource, then in method  300  returns to act  304  via act  320 . In act  320 , the counting mechanism X is reset to 0 and the latest picked facility/resource is removed from the list of possible facilities/resources. Then, acts  304  through  314  are conducted and another facility/resource is picked and one or more clients assigned to it.  
         [0165]    In act  316 , a local comparison is conducted for assigned clients and the facilities/resources picked thus far to determine if one or more of the clients can be reassigned to another picked facility/resource to save costs. Thus, for example, if client  204   b  was originally assigned to facility  202   a , and now facility  202   c  has also been picked and assigned other clients, then in act  316  a comparison of costs  208   a  and  208   c  is made to determine if client  204   b  should be reassigned to client  204   c . In this example, let us assume that cost  208   a  for client  204   b  to access facility  202   a  has a value of “150”, and cost  208   c  for client  204   b  to access facility  202   c  has a value of “120”. Then, it makes sense to reassign client  204   b  to facility  202   c  since there is a savings of 150-120=30. Such “savings” may also be considered in act  308  during subsequent cost determinations.  
         [0166]    Once all of the clients have been assigned to a facility/resource, then in act  322  picked facilities that no longer have clients assigned to them are removed as build candidates. Also, in act  322 , decisions can be made to reassign clients from under-used facilities/resources to other build candidate facilities/resources. Thus, for example, if picked (build candidate) facility  202   a  only has two clients assigned to it and the other picked (build candidate) facilities have hundreds of clients each, then each of the clients assigned to facility  202   a  may be reassigned to another facility and facility  202   a  essentially “unpicked”. Thus, act  322  may include logic to ensure that certain threshold criteria are satisfied by the resulting picked (build candidate) facilities.  
       CONCLUSION  
       [0167]    The above novel algorithm presented herein provides further improvements over previously known results dependent upon the contemporary primal-dual algorithm. In particular, for example, in certain implementations, the improved algorithm provides a factor 4 for K-median problems, and a factor 1.57 for the incapacitated facility location problem. To get these even more outstanding results, for example, one may further implement scaling of the facility costs via preprocessing and eventually complete a local search and greedy augmentation in the end.  
         [0168]    Although the invention has been described in language specific to structural features and/or methodological acts, it is to be understood that the invention defined in the appended claims is not necessarily limited to the specific features or steps described.