Cygan, Marek ;
Kociumaka, Tomasz
Approximating Upper DegreeConstrained Partial Orientations
Abstract
In the Upper DegreeConstrained Partial Orientation (UDPO) problem we are given an undirected graph G=(V,E), together with two degree constraint functions d^,d^+:V > N. The goal is to orient as many edges as possible, in such a way that for each vertex v in V the number of arcs entering v is at most d^(v), whereas the number of arcs leaving v is at most d^+(v). This problem was introduced by Gabow [SODA'06], who proved it to be MAXSNPhard (and thus APXhard). In the same paper Gabow presented an LPbased iterative rounding 4/3approximation algorithm.
As already observed by Gabow, the problem in question is a special case of the classic 3Dimensional Matching, which in turn is a special case of the kSet Packing problem. Back in 2006 the best known polynomial time approximation algorithm for 3Dimensional Matching was a simple local search by Hurkens and Schrijver [SIDMA'89], the approximation ratio of which is (3+epsilon)/2; hence the algorithm of Gabow was an improvement over the approach brought from the more general problems.
In this paper we show that the UDPO problem when cast as 3Dimensional Matching admits a special structure, which is obliviously exploited by the known approximation algorithms for kSet Packing. In fact, we show that already the localsearch routine of Hurkens and Schrijver gives (4+epsilon)/3approximation when used for the instances coming from UDPO. Moreover, the recent approximation algorithm for 3Set Packing [Cygan, FOCS'13] turns out to be a (5+epsilon)/4approximation for UDPO. This improves over 4/3 as the best ratio known up to date for UDPO.
BibTeX  Entry
@InProceedings{cygan_et_al:LIPIcs:2015:5304,
author = {Marek Cygan and Tomasz Kociumaka},
title = {{Approximating Upper DegreeConstrained Partial Orientations}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
pages = {212224},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897897},
ISSN = {18688969},
year = {2015},
volume = {40},
editor = {Naveen Garg and Klaus Jansen and Anup Rao and Jos{\'e} D. P. Rolim},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5304},
URN = {urn:nbn:de:0030drops53040},
doi = {10.4230/LIPIcs.APPROXRANDOM.2015.212},
annote = {Keywords: graph orientations, degreeconstrained orientations, approximation algorithm, local search}
}
13.08.2015
Keywords: 

graph orientations, degreeconstrained orientations, approximation algorithm, local search 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Issue date: 

2015 
Date of publication: 

13.08.2015 