## Abstract

In this paper we theoretically study the minimum Differentially Resolving Set (DRS) problem derived from the classical sensor placement optimization problem in network source locating. A DRS of a graph G = (V,E) is defined as a subset S ⊆ V where any two elements in V can be distinguished by their different differential characteristic sets defined on S. The minimum DRS problem aims to find a DRS S in the graph G with minimum total weightΣ v∈S w(v). In this paper we establish a group of Integer Linear Programming (ILP) models as the solution. By the weighted set cover theory, we propose an approximation algorithm with the Θ(ln n) approximability for the minimum DRS problem on general graphs, where n is the graph size.

Original language | English |
---|---|

Title of host publication | AAAI 2016 |

Subtitle of host publication | Proceedings of the 30th AAAI Conference on Artificial Intelligence |

Place of Publication | Palo Alto, CA |

Publisher | Association for the Advancement of Artificial Intelligence |

Pages | 79-85 |

Number of pages | 7 |

ISBN (Electronic) | 9781577357605 |

Publication status | Published - 2016 |

Externally published | Yes |

Event | 30th AAAI Conference on Artificial Intelligence, AAAI 2016 - Phoenix, United States Duration: 12 Feb 2016 → 17 Feb 2016 |

### Conference

Conference | 30th AAAI Conference on Artificial Intelligence, AAAI 2016 |
---|---|

Country/Territory | United States |

City | Phoenix |

Period | 12/02/16 → 17/02/16 |

## Keywords

- Differentially Resolving Set
- Diffusion Source Inferenc
- Networks