Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Fekete, Sándor P.
Friedrichs, Stephan
Kröller, Alexander
Schmidt, Christiane

dblp
dblp
dblp
dblp

Not MPG Author(s):

Fekete, Sándor P.
Friedrichs, Stephan
Kröller, Alexander
Schmidt, Christiane

Editor(s):

Du, Ding-Zhu
Zhang, Guochuan

dblp
dblp

Not MPII Editor(s):

Du, Ding-Zhu
Zhang, Guochuan

BibTeX cite key*:

ffks-ffagp-13

Title, Booktitle

Title*:

Facets for Art Gallery Problems

Booktitle*:

Computing and Combinatorics

Event, URLs

URL of the conference:

http://www.cs.zju.edu.cn/algo/cocoon2013/

URL for downloading the paper:


Event Address*:

Hangzhou, China

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

21 June 2013

Event End Date:

23 June 2013

Publisher

Name*:

Springer

URL:

http://www.springer.com/

Address*:

Berlin

Type:


Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:

7936

Number:


Month:

June

Pages:

208-220

Year*:

2013

VG Wort Pages:


ISBN/ISSN:

978-3-642-38767-8

Sequence Number:


DOI:

10.1007/978-3-642-38768-5_20



Note, Abstract, ©


(LaTeX) Abstract:

We demonstrate how polyhedral methods of mathematical programming can be developed for and applied to computing optimal solutions for large instances of a classical geometric optimization problem with an uncountable number of constraints and variables.

The Art Gallery Problem (AGP) asks for placing a minimum number of stationary guards in a polygonal region $P$, such that all points in $P$ are guarded. The AGP is NP-hard, even to approximate. Due to the infinite number of points to be guarded as well as possible guard positions, applying mathematical programming methods for computing provably optimal solutions is far from straightforward.

In this paper, we use an iterative primal-dual relaxation approach for solving AGP instances to optimality. At each stage, a pair of LP relaxations for a finite candidate subset of primal covering and dual packing constraints and variables is considered; these correspond to possible guard positions and points that are to be guarded.

Of particular interest are additional cutting planes for eliminating fractional solutions. We identify two classes of facets, based on Edge Cover and Set Cover (SC) inequalities. Solving the separation problem for the latter is NP-complete, but exploiting the underlying geometric structure of the AGP, we show that large subclasses of fractional SC solutions cannot occur for the AGP. This allows us to separate the relevant subset of facets in polynomial time.

Finally, we characterize all facets for finite AGP relaxations with coefficients in ${0, 1, 2}$. We demonstrate the practical usefulness of our approach with improved solution quality and speed for a wide array of large benchmark instances.

URL for the Abstract:

http://arxiv.org/abs/1308.4670

Keywords:

Art Gallery Problem, geometric optimization, algorithm engineering, set cover polytope, solving NP-hard problem instances to optimality



Download
Access Level:

Internal

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

External Affiliations:

TU Braunschweig

Audience:

experts only

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{ffks-ffagp-13,
AUTHOR = {Fekete, S{\'a}ndor P. and Friedrichs, Stephan and Kr{\"o}ller, Alexander and Schmidt, Christiane},
EDITOR = {Du, Ding-Zhu and Zhang, Guochuan},
TITLE = {Facets for Art Gallery Problems},
BOOKTITLE = {Computing and Combinatorics},
PUBLISHER = {Springer},
YEAR = {2013},
VOLUME = {7936},
PAGES = {208--220},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Hangzhou, China},
MONTH = {June},
ISBN = {978-3-642-38767-8},
DOI = {10.1007/978-3-642-38768-5_20},
}


Entry last modified by Stephan Friedrichs, 10/08/2014
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Stephan Friedrichs
Created
10/08/2014 02:30:34 PM
Revision
1.
0.


Editor
Stephan Friedrichs
Stephan Friedrichs


Edit Date
10/08/2014 04:11:43 PM
10/08/2014 02:30:34 PM