English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Facility location is a prominent optimization problem that has inspired alarge quantity of both theoretical and practical studies in combinatorialoptimization. Although the problem has been investigated under various settingsreflecting typical structures within the optimization problems of practicalinterest, little is known on how the problem behaves in conjunction with parityconstraints. This shortfall of understanding was rather disturbing when weconsider the central role of parity in the field of combinatorics. In thispaper, we present the first constant-factor approximation algorithm for thefacility location problem with parity constraints. We are given as the input ametric on a set of facilities and clients, the opening cost of each facility,and the parity requirement--odd, even, or unconstrained--of every facility inthis problem. The objective is to open a subset of facilities and assign everyclient to an open facility so as to minimize the sum of the total opening costsand the assignment distances, but subject to the condition that the number ofclients assigned to each open facility must have the same parity as itsrequirement.  Although the unconstrained facility location problem as a relaxation for thisparity-constrained generalization has unbounded gap, we demonstrate that ityields a structured solution whose parity violation can be corrected at smallcost. This correction is prescribed by a T-join on an auxiliary graphconstructed by the algorithm. This graph does not satisfy the triangleinequality, but we show that a carefully chosen set of shortcutting operationsleads to a cheap and sparse T-join. Finally, we bound the correction cost byexhibiting a combinatorial multi-step construction of an upper bound. We alsopresent the first constant-factor approximation algorithm for theparity-constrained k-center problem, the bottleneck optimization variant.

Constant-Factor Approximation Algorithms for Parity-Constrained Facility Location Problems