2026-07-26T00:33:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5304 2024-03-06T10:36:16Z ddc:004 open_access

Approximating Upper Degree-Constrained Partial Orientations Cygan, Marek Kociumaka, Tomasz graph orientations degree-constrained orientations approximation algorithm local search In the Upper Degree-Constrained 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 MAXSNP-hard (and thus APX-hard). In the same paper Gabow presented an LP-based iterative rounding 4/3-approximation algorithm. As already observed by Gabow, the problem in question is a special case of the classic 3-Dimensional Matching, which in turn is a special case of the k-Set Packing problem. Back in 2006 the best known polynomial time approximation algorithm for 3-Dimensional 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 3-Dimensional Matching admits a special structure, which is obliviously exploited by the known approximation algorithms for k-Set Packing. In fact, we show that already the local-search routine of Hurkens and Schrijver gives (4+epsilon)/3-approximation when used for the instances coming from UDPO. Moreover, the recent approximation algorithm for 3-Set Packing [Cygan, FOCS'13] turns out to be a (5+epsilon)/4-approximation for UDPO. This improves over 4/3 as the best ratio known up to date for UDPO. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marek Cygan and Tomasz Kociumaka 2015 Is Part Of LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2015.212 urn:nbn:de:0030-drops-53040 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.212 eng https://creativecommons.org/licenses/by/3.0/legalcode