Cited By
View all- Kutucu HGursoy AKurt MNuriyev U(2020)The band collocation problemJournal of Combinatorial Optimization10.1007/s10878-020-00576-240:2(454-481)Online publication date: 1-Jun-2020
A 0.5358-approximation for Bandpass-2
Pages 612 - 626
Abstract
The Bandpass-2 problem is a variant of the maximum traveling salesman problem arising from optical communication networks using wavelength-division multiplexing technology, in which the edge weights are dynamic rather than fixed. The previously best approximation algorithm for this NP-hard problem has a worst-case performance ratio of $$\frac{227}{426}.$$227426. Here we present a novel scheme to partition the edge set of a 4-matching into a number of subsets, such that the union of each of them and a given matching is an acyclic 2-matching. Such a partition result takes advantage of a known structural property of the optimal solution, leading to a $$\frac{70-\sqrt{2}}{128}\approx 0.5358$$70-2128 0.5358-approximation algorithm for the Bandpass-2 problem.
References
[1]
Anstee RP (1987) A polynomial algorithm for b -matching: an alternative approach. Inf Process Lett 24:153-157.
[2]
Arkin EM, Hassin R (1998) On local search for weighted packing problems. Math Oper Res 23:640-648.
[3]
Babayev DA, Bell GI, Nuriyev UG (2009) The bandpass problem: combinatorial optimization and library of problems. J Comb Optim 18:151-172.
[4]
Bell GI, Babayev DA (2004) Bandpass problem. In: Annual INFORMS meeting, Denver, CO, USA, October 2004.
[5]
Chandra B, Halldórsson MM (1999) Greedy local improvement and weighted set packing approximation. In: ACM-SIAM proceedings of the tenth annual symposium on discrete algorithms (SODA'99), pp 169-176.
[6]
Chen Z-Z, Wang L (2012) An improved approximation algorithm for the bandpass-2 problem. In: Proceedings of the 6th annual international conference on combinatorial optimization and applications (COCOA 2012), LNCS, vol 7402, pp 185-196.
[7]
Chen Z-Z, Okamoto Y, Wang L (2005) Improved deterministic approximation algorithms for Max TSP. Inf Process Lett 95:333-342.
[8]
Diestel R (2005) Graph theory, 3rd edn. Springer, New York.
[9]
Gabow H (1983) An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In: Proceedings of the 15th annual ACM symposium on theory of computing (STOC'83), pp 448-456.
[10]
Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman and Company, San Francisco.
[11]
Harary F (1969) Graph theory. Addison-Wesley, Reading.
[12]
Hassin R, Rubinstein S (2000) Better approximations for Max TSP. Inf Process Lett 75:181-186.
[13]
Lin G (2011) On the Bandpass problem. J Comb Optim 22:71-77.
[14]
Miller DL, Pekny JF (1995) A staged primal-dual algorithm for perfect b -matching with edge capacities. ORSA J Comput 7:298-320.
[15]
Paluch KE, Mucha M, Madry A (2009) A 7/9-approximation algorithm for the maximum traveling salesman problem. In: Proceedings of the 12th international workshop on APPROX and the 13th international workshop on RANDOM, LNCS, vol 5687, pp 298-311.
[16]
Serdyukov AI (1984) An algorithms for with an estimate for the traveling salesman problem of the maximum. Upravlyaemye Sistemy 25:80-86.
[17]
Tarjan RE (1975) Efficiency of a good but not linear set union algorithm. J ACM 22:215-225.
[18]
Tong W, Goebel R, Ding W, Lin G (2012) An improved approximation algorithm for the bandpass problem. In: Proceedings of the joint conference of the sixth international frontiers of algorithmics workshop and the eighth international conference on algorithmic aspects of information and management (FAW-AAIM 2012), LNCS, vol 7285, pp 351-358.
[19]
Tong W, Chen Z-Z, Wang L, Xu Y, Xu J, Goebel R, Lin G (2013) An approximation algorithm for the bandpass-2 problem. arXiv 1307:7089 (under review).
- A 0.5358-approximation for Bandpass-2
Recommendations
An improved approximation algorithm for the bandpass problem
FAW-AAIM'12: Proceedings of the 6th international Frontiers in Algorithmics, and Proceedings of the 8th international conference on Algorithmic Aspects in Information and ManagementThe general Bandpass-<em>B</em> problem is NP-hard and can be approximated by a reduction into the <em>B</em> -set packing problem, with a worst case performance ratio of <em>O</em> (<em>B</em> 2). When <em>B</em> =2, a maximum weight matching gives a 2-...
Improved Approximation Algorithms for Minimum Cost Node-Connectivity Augmentation Problems
Let źG(s, t) denote the maximum number of pairwise internally disjoint st-paths in a graph G = (V, E). For a set T⊆V$T \subseteq V$ of terminals, G is k-T-connected if źG(s, t) ź k for all s, t ź T; if T = V then G is k-connected. Given a root node s, G ...
A simple approximation algorithm for minimum weight partial connected set cover
This paper studies the minimum weight partial connected set cover problem (PCSC). Given an element set U, a collection $${\mathcal {S}}$$S of subsets of U, a weight function c : $${\mathcal {S}} \rightarrow {\mathbb {Q}}^{+}$$SźQ+, a connected graph $$G_...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Copyright © 2015 Springer Science+Business Media New York.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 01 October 2015
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 20 Jan 2025
Other Metrics
Citations
Cited By
View all- Kutucu HGursoy AKurt MNuriyev U(2020)The band collocation problemJournal of Combinatorial Optimization10.1007/s10878-020-00576-240:2(454-481)Online publication date: 1-Jun-2020