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