Nonlinear combinatorial optimization

Preface......Page 5
Contents......Page 7
 1 A Property of Minimum Spanning Tree......Page 9
 2 Symmetric Topological Control......Page 10
 3 Asymmetric Topological Control......Page 17
 4 Broadcast......Page 27
 5 Asymmetric Power Requirement......Page 38
 References......Page 41
 1 Discrete Newton Method......Page 44
  2.1 Linear Fractional Combinatorial Optimization......Page 50
  2.2 Inverse Combinatorial Problems......Page 55
  2.3 Bottleneck Expansion......Page 59
 References......Page 63
 1 Submodular Function......Page 64
   1.2.1 Pseudo-Boolean function......Page 65
   1.2.2 Partial Derivative for Pseudo-Boolean Function......Page 66
  2.1 Convex Envelope/Closure......Page 67
  2.2 Lovász Extension......Page 69
   2.2.1 Definition......Page 70
   2.2.2 Kuhn's Triangulation: Geometric View of (9)–(10)......Page 71
   2.2.3 Lovász Extension as Choquet Expectation......Page 72
   2.2.4 Application......Page 73
   2.2.5 Lovász Extension of Pseudo-Boolean Function Represented in Multilinear Form......Page 74
   2.2.7 Lovász Extension of Submodular Function......Page 75
  2.3 Properties of Lovász Extension......Page 77
  2.4 Concave Closure......Page 78
  2.5 Multilinear Extension......Page 79
   2.5.2 Properties of the Multilinear Extension......Page 80
  2.6 Relationship Among Extensions......Page 83
 3 Simultaneous Approximation of Multi-Criteria Submodular Function Maximization ch3:du2014simultaneous......Page 84
 References......Page 85
 1 Introduction......Page 87
 2 Basic Definitions and Properties......Page 88
  2.1 Motivation......Page 89
  2.2 Definition......Page 91
  2.3 Local Submodularity......Page 94
  3.1 Extensions of Submodular Set Function......Page 96
  3.2 Polymatroid Optimization......Page 99
  3.3 Minimization of Submodular Set Function......Page 102
  3.4 Maximization of Submodular Set Function......Page 105
  3.5 Multi-Linear Relaxation and Submodular Function Maximization......Page 110
  4.1 L-Convexity......Page 116
  4.2 L-Convexity in Dynamic Inventory System......Page 120
  4.3 Online/Dynamic Matching......Page 123
 References......Page 126
Thresholding Methods for Streaming Submodular Maximization with a Cardinality Constraint and Its Variants......Page 128
 1 Introduction......Page 129
  2.1 Sieve-Streaming in Case the Optimum is Known......Page 130
  2.2 Sieve-Streaming in Case We Know the Maximum......Page 132
  3.1 An (0.333-ε) Approximation Algorithm for Submodular Maximization over Sliding Windows......Page 133
   3.1.1 Stream Algorithm for Streaming Submodular Maximization with Cardinality Constraint......Page 134
   3.1.2 A Submodular Smooth Histograms Algorithm for Streaming Submodular Maximization over Sliding Windows......Page 135
  3.2 A Partitioned Thresholding Approach for Streaming Robust Submodular Maximization (SRSW)......Page 136
  3.3 A Robust-Streaming Algorithm for Deletion-Robust Submodular Maximization......Page 138
 4 Thresholding Algorithms for Nonsubmodular Maximization......Page 140
 5 Summarizations of Thresholding Methods for Other Submodular Maximization Applications......Page 142
 References......Page 144
 1 Introduction......Page 146
 2 Supermodular Degree......Page 147
 3 Curvature......Page 149
 4 Local Optimality......Page 152
 5 Data-Dependent Approximation......Page 154
 References......Page 155
 1 Introduction......Page 158
  2.1 Block-Structured Integer Programs......Page 159
  2.3 An Iterative Augmentation Framework......Page 162
 3 Optimizing over a Linear Objective......Page 163
  3.1 Iterative Augmentation......Page 164
  3.2 Designing the Graver-Best Oracle......Page 165
   3.2.2 Tree-Fold IP......Page 166
   3.2.3 Multistage Stochastic IP......Page 167
   3.2.4 4-Block n-Fold IP......Page 168
  4.1 Minimizing an Appropriate Convex Function......Page 169
   4.1.2 Convex Splittable Two-Stage Stochastic IP......Page 171
  4.2 Maximizing an Appropriate Convex Function for n-Fold IP......Page 172
  5.1 Scheduling......Page 173
  5.2 Computational Social Choice......Page 176
  5.3 Multiple TSP on a Tree......Page 178
  5.4 Other Applications......Page 179
 6 Conclusion......Page 180
 References......Page 181
 1 Introduction......Page 183
  1.1 Organization......Page 184
 2 Online Primal Dual for Linear Objectives......Page 185
  2.2 Relaxed Complementary Slackness......Page 186
  2.4 Online Primal Dual Analysis......Page 187
  3.1 Conjugates......Page 188
  3.2 An Example: Online Auction of an Item with Production Cost......Page 189
  3.4 High-Level Plan......Page 191
  3.6 (Approximate) Complementary Pairs......Page 192
  3.8 Primal Dual Analysis......Page 193
  4.1 Problem Definition......Page 194
  4.3 Online Primal Dual Algorithms......Page 195
  4.5 An Example: Additive Agents with Budgets......Page 196
  5.1 Problem Definition......Page 198
  5.3 A Simple Greedy Algorithm......Page 200
  5.4 Online Primal Dual Analysis......Page 201
  5.5 Better Online Primal Dual Algorithms......Page 202
 6 Application: Online Covering and Packing Problems with Convex Objectives......Page 203
  6.2 Relaxed Optimality Conditions......Page 204
  6.4 Online Primal Dual Analysis......Page 205
 References......Page 208
Solving Combinatorial Problems with Machine Learning Methods......Page 210
 1 Introduction......Page 211
  2.1 Recurrent Neural Network......Page 213
  2.2 Encoder–Decoder Model......Page 214
  2.3 Attention Mechanism......Page 215
  3.1 Pointer Network......Page 217
   3.1.1 Experiments......Page 218
  3.2 Multi-Pointer Network......Page 219
   3.2.1 Experiments......Page 220
   3.3.1 Experiments......Page 221
 4 Reinforcement Learning for Solving Some Combinatorial Optimization Problems......Page 222
   4.1.1 Traveling Salesman Problem (TSP)......Page 225
   4.1.2 Maximum Cut (MAXCUT) and Minimum Vertex Cover (MVC)......Page 228
 References......Page 230
Modeling Malware Propagation Dynamics and Developing Prevention Methods in Wireless Sensor Networks......Page 233
 1 Introduction......Page 234
  2.1 Introduction of Malware Propagation in WSNs......Page 236
  2.2 Overview of Modeling and Prevention......Page 237
   2.2.2 Pulse Immunization Model of Malware......Page 238
   2.2.3 Cost-Efficient Prevention Methods......Page 239
   2.2.4 Information Propagation Dynamics in Heterogeneous Network he2017cost......Page 240
  2.3 Reaction–diffusion Modeling of Malware Propagation in MWSN wang2013reaction......Page 241
  2.4 Pulse Immunization Model......Page 243
  2.5 Emotion Contagion in the Human Population in Emergencies wang2016computational......Page 245
  2.6 Optimal Control Method for Information Diffusion......Page 246
 3 Discrete Models Based on Cellular Automata......Page 247
 4 Conclusions and Future Work......Page 248
 References......Page 249
 1 Introduction......Page 253
  1.2 Submodular and Nonsubmodular Functions......Page 254
  1.3 Diffusion Models......Page 255
   1.3.2 Linear Threshold Model......Page 256
 2 Related Work......Page 257
 3 Problem Formulation......Page 258
  3.2 Influence Maximization in Hypergraphs......Page 259
  3.3 Example Objective Function Formulation......Page 260
  4.1 RIS Sampling......Page 261
 5 Sandwich Approximation Framework......Page 262
 6 Conclusion......Page 264
 References......Page 265
 1 Active Friending......Page 267
 3 Group Friending......Page 271
 References......Page 272
 1 Introduction......Page 275
  1.1 Positive Content Maximization......Page 276
 2 Related Works......Page 277
   2.2.1 Boosting Content Spread......Page 278
   2.2.2 Negative Content Minimization......Page 279
  3.2 Content Spread Maximization......Page 280
  3.3 Negative Content Minimization......Page 282
  4.2 Submodularity......Page 283
 5 Conclusion......Page 284
 References......Page 285
 1 Introduction......Page 287
 2 Related Work......Page 289
  3.1 Activity Maximization......Page 290
  3.2 Interaction-Aware Influence Maximization......Page 292
 4 A Method for Interaction-Aware Influence Maximization......Page 293
 References......Page 295
 1 Introduction......Page 297
 3 Multi-Document Summarization Approaches......Page 299
  3.1 Statistical Approaches......Page 300
  3.3 Graph-Based Approaches......Page 301
  3.4 Machine Learning Based Approaches......Page 302
  3.5 Optimization Based Approaches......Page 304
  4.1 Diversity in Summary......Page 305
  4.2 Problem Formulation......Page 306
 References......Page 308
 1 Who Buys A May also Like to Buy B......Page 311
 2 Knapsack-Constrained Submodular Maximization......Page 312
 References......Page 316