doc/references.bib
author Peter Kovacs <kpeter@inf.elte.hu>
Thu, 12 Nov 2009 23:26:13 +0100
changeset 806 fa6f37d7a25b
parent 754 2de0fc630899
child 904 c279b19abc62
permissions -rw-r--r--
Entirely rework CapacityScaling (#180)

- Use the new interface similarly to NetworkSimplex.
- Rework the implementation using an efficient internal structure
for handling the residual network. This improvement made the
code much faster (up to 2-5 times faster on large graphs).
- Handle GEQ supply type (LEQ is not supported).
- Handle negative costs for arcs of finite capacity.
(Note that this algorithm cannot handle arcs of negative cost
and infinite upper bound, thus it returns UNBOUNDED if such
an arc exists.)
- Extend the documentation.
     1 %%%%% Defining LEMON %%%%%
     2 
     3 @misc{lemon,
     4   key =          {LEMON},
     5   title =        {{LEMON} -- {L}ibrary for {E}fficient {M}odeling and
     6                   {O}ptimization in {N}etworks},
     7   howpublished = {\url{http://lemon.cs.elte.hu/}},
     8   year =         2009
     9 }
    10 
    11 @misc{egres,
    12   key =          {EGRES},
    13   title =        {{EGRES} -- {E}gerv{\'a}ry {R}esearch {G}roup on
    14                   {C}ombinatorial {O}ptimization},
    15   url =          {http://www.cs.elte.hu/egres/}
    16 }
    17 
    18 @misc{coinor,
    19   key =          {COIN-OR},
    20   title =        {{COIN-OR} -- {C}omputational {I}nfrastructure for
    21                   {O}perations {R}esearch},
    22   url =          {http://www.coin-or.org/}
    23 }
    24 
    25 
    26 %%%%% Other libraries %%%%%%
    27 
    28 @misc{boost,
    29   key =          {Boost},
    30   title =        {{B}oost {C++} {L}ibraries},
    31   url =          {http://www.boost.org/}
    32 }
    33 
    34 @book{bglbook,
    35   author =       {Jeremy G. Siek and Lee-Quan Lee and Andrew
    36                   Lumsdaine},
    37   title =        {The Boost Graph Library: User Guide and Reference
    38                   Manual},
    39   publisher =    {Addison-Wesley},
    40   year =         2002
    41 }
    42 
    43 @misc{leda,
    44   key =          {LEDA},
    45   title =        {{LEDA} -- {L}ibrary of {E}fficient {D}ata {T}ypes and
    46                   {A}lgorithms},
    47   url =          {http://www.algorithmic-solutions.com/}
    48 }
    49 
    50 @book{ledabook,
    51   author =       {Kurt Mehlhorn and Stefan N{\"a}her},
    52   title =        {{LEDA}: {A} platform for combinatorial and geometric
    53                   computing},
    54   isbn =         {0-521-56329-1},
    55   publisher =    {Cambridge University Press},
    56   address =      {New York, NY, USA},
    57   year =         1999
    58 }
    59 
    60 
    61 %%%%% Tools that LEMON depends on %%%%%
    62 
    63 @misc{cmake,
    64   key =          {CMake},
    65   title =        {{CMake} -- {C}ross {P}latform {M}ake},
    66   url =          {http://www.cmake.org/}
    67 }
    68 
    69 @misc{doxygen,
    70   key =          {Doxygen},
    71   title =        {{Doxygen} -- {S}ource code documentation generator
    72                   tool},
    73   url =          {http://www.doxygen.org/}
    74 }
    75 
    76 
    77 %%%%% LP/MIP libraries %%%%%
    78 
    79 @misc{glpk,
    80   key =          {GLPK},
    81   title =        {{GLPK} -- {GNU} {L}inear {P}rogramming {K}it},
    82   url =          {http://www.gnu.org/software/glpk/}
    83 }
    84 
    85 @misc{clp,
    86   key =          {Clp},
    87   title =        {{Clp} -- {Coin-Or} {L}inear {P}rogramming},
    88   url =          {http://projects.coin-or.org/Clp/}
    89 }
    90 
    91 @misc{cbc,
    92   key =          {Cbc},
    93   title =        {{Cbc} -- {Coin-Or} {B}ranch and {C}ut},
    94   url =          {http://projects.coin-or.org/Cbc/}
    95 }
    96 
    97 @misc{cplex,
    98   key =          {CPLEX},
    99   title =        {{ILOG} {CPLEX}},
   100   url =          {http://www.ilog.com/}
   101 }
   102 
   103 @misc{soplex,
   104   key =          {SoPlex},
   105   title =        {{SoPlex} -- {T}he {S}equential {O}bject-{O}riented
   106                   {S}implex},
   107   url =          {http://soplex.zib.de/}
   108 }
   109 
   110 
   111 %%%%% General books %%%%%
   112 
   113 @book{amo93networkflows,
   114   author =       {Ravindra K. Ahuja and Thomas L. Magnanti and James
   115                   B. Orlin},
   116   title =        {Network Flows: Theory, Algorithms, and Applications},
   117   publisher =    {Prentice-Hall, Inc.},
   118   year =         1993,
   119   month =        feb,
   120   isbn =         {978-0136175490}
   121 }
   122 
   123 @book{schrijver03combinatorial,
   124   author =       {Alexander Schrijver},
   125   title =        {Combinatorial Optimization: Polyhedra and Efficiency},
   126   publisher =    {Springer-Verlag},
   127   year =         2003,
   128   isbn =         {978-3540443896}
   129 }
   130 
   131 @book{clrs01algorithms,
   132   author =       {Thomas H. Cormen and Charles E. Leiserson and Ronald
   133                   L. Rivest and Clifford Stein},
   134   title =        {Introduction to Algorithms},
   135   publisher =    {The MIT Press},
   136   year =         2001,
   137   edition =      {2nd}
   138 }
   139 
   140 @book{stroustrup00cpp,
   141   author =       {Bjarne Stroustrup},
   142   title =        {The C++ Programming Language},
   143   edition =      {3rd},
   144   publisher =    {Addison-Wesley Professional},
   145   isbn =         0201700735,
   146   month =        {February},
   147   year =         2000
   148 }
   149 
   150 
   151 %%%%% Maximum flow algorithms %%%%%
   152 
   153 @article{edmondskarp72theoretical,
   154   author =       {Jack Edmonds and Richard M. Karp},
   155   title =        {Theoretical improvements in algorithmic efficiency
   156                   for network flow problems},
   157   journal =      {Journal of the ACM},
   158   year =         1972,
   159   volume =       19,
   160   number =       2,
   161   pages =        {248-264}
   162 }
   163 
   164 @article{goldberg88newapproach,
   165   author =       {Andrew V. Goldberg and Robert E. Tarjan},
   166   title =        {A new approach to the maximum flow problem},
   167   journal =      {Journal of the ACM},
   168   year =         1988,
   169   volume =       35,
   170   number =       4,
   171   pages =        {921-940}
   172 }
   173 
   174 @article{dinic70algorithm,
   175   author =       {E. A. Dinic},
   176   title =        {Algorithm for solution of a problem of maximum flow
   177                   in a network with power estimation},
   178   journal =      {Soviet Math. Doklady},
   179   year =         1970,
   180   volume =       11,
   181   pages =        {1277-1280}
   182 }
   183 
   184 @article{goldberg08partial,
   185   author =       {Andrew V. Goldberg},
   186   title =        {The Partial Augment-Relabel Algorithm for the
   187                   Maximum Flow Problem},
   188   journal =      {16th Annual European Symposium on Algorithms},
   189   year =         2008,
   190   pages =        {466-477}
   191 }
   192 
   193 @article{sleator83dynamic,
   194   author =       {Daniel D. Sleator and Robert E. Tarjan},
   195   title =        {A data structure for dynamic trees},
   196   journal =      {Journal of Computer and System Sciences},
   197   year =         1983,
   198   volume =       26,
   199   number =       3,
   200   pages =        {362-391}
   201 }
   202 
   203 
   204 %%%%% Minimum mean cycle algorithms %%%%%
   205 
   206 @article{karp78characterization,
   207   author =       {Richard M. Karp},
   208   title =        {A characterization of the minimum cycle mean in a
   209                   digraph},
   210   journal =      {Discrete Math.},
   211   year =         1978,
   212   volume =       23,
   213   pages =        {309-311}
   214 }
   215 
   216 @article{dasdan98minmeancycle,
   217   author =       {Ali Dasdan and Rajesh K. Gupta},
   218   title =        {Faster Maximum and Minimum Mean Cycle Alogrithms for
   219                   System Performance Analysis},
   220   journal =      {IEEE Transactions on Computer-Aided Design of
   221                   Integrated Circuits and Systems},
   222   year =         1998,
   223   volume =       17,
   224   number =       10,
   225   pages =        {889-899}
   226 }
   227 
   228 
   229 %%%%% Minimum cost flow algorithms %%%%%
   230 
   231 @article{klein67primal,
   232   author =       {Morton Klein},
   233   title =        {A primal method for minimal cost flows with
   234                   applications to the assignment and transportation
   235                   problems},
   236   journal =      {Management Science},
   237   year =         1967,
   238   volume =       14,
   239   pages =        {205-220}
   240 }
   241 
   242 @article{goldberg89cyclecanceling,
   243   author =       {Andrew V. Goldberg and Robert E. Tarjan},
   244   title =        {Finding minimum-cost circulations by canceling
   245                   negative cycles},
   246   journal =      {Journal of the ACM},
   247   year =         1989,
   248   volume =       36,
   249   number =       4,
   250   pages =        {873-886}
   251 }
   252 
   253 @article{goldberg90approximation,
   254   author =       {Andrew V. Goldberg and Robert E. Tarjan},
   255   title =        {Finding Minimum-Cost Circulations by Successive
   256                   Approximation},
   257   journal =      {Mathematics of Operations Research},
   258   year =         1990,
   259   volume =       15,
   260   number =       3,
   261   pages =        {430-466}
   262 }
   263 
   264 @article{goldberg97efficient,
   265   author =       {Andrew V. Goldberg},
   266   title =        {An Efficient Implementation of a Scaling
   267                   Minimum-Cost Flow Algorithm},
   268   journal =      {Journal of Algorithms},
   269   year =         1997,
   270   volume =       22,
   271   number =       1,
   272   pages =        {1-29}
   273 }
   274 
   275 @article{bunnagel98efficient,
   276   author =       {Ursula B{\"u}nnagel and Bernhard Korte and Jens
   277                   Vygen},
   278   title =        {Efficient implementation of the {G}oldberg-{T}arjan
   279                   minimum-cost flow algorithm},
   280   journal =      {Optimization Methods and Software},
   281   year =         1998,
   282   volume =       10,
   283   pages =        {157-174}
   284 }
   285 
   286 @book{dantzig63linearprog,
   287   author =       {George B. Dantzig},
   288   title =        {Linear Programming and Extensions},
   289   publisher =    {Princeton University Press},
   290   year =         1963
   291 }
   292 
   293 @mastersthesis{kellyoneill91netsimplex,
   294   author =       {Damian J. Kelly and Garrett M. O'Neill},
   295   title =        {The Minimum Cost Flow Problem and The Network
   296                   Simplex Method},
   297   school =       {University College},
   298   address =      {Dublin, Ireland},
   299   year =         1991,
   300   month =        sep,
   301 }