article

Algorithms with large domination ratio

Authors:

Michael KrivelevichAuthors Info & Claims

Journal of Algorithms, Volume 50, Issue 1

Pages 118 - 131

https://doi.org/10.1016/j.jalgor.2003.09.003

Published: 01 January 2004 Publication History

Abstract

Let P be an optimization problem, and let A be an approximation algorithm for P. The domination ratio domr(A, n) is the maximum real q such that the solution x(I) obtained by A for any instance I of P of size n is not worse than at least a fraction q of the feasible solutions of I. We describe a deterministic, polynomial-time algorithm with domination ratio 1 - o(1) for the partition problem, and a deterministic, polynomial-time algoritiun with domination ratio Ω(1) for the MaxCut problem and for some far-reaching extensions of it, including Max-r-Sat, for each fixed r. The techniques combine combinatorial and probabilistic methods with tools from harmonic analysis.

References

[1]

{1} N. Alon, Bipartite subgraphs, Combinatorica 16 (1996) 301-311.

[2]

{2} N. Alon, Voting paradoxes and digraphs realizations, Adv. in Appl. Math. 29 (2002) 126-135.

[3]

{3} N. Alon, B. Bollobás, M. Krivelevich, B. Sudakov, Maximum cuts and judicious partitions in graphs without short cycles, J. Combin. Theory Ser. B 88 (2003) 329-346.

[4]

{4} N. Alon, J.H. Spencer, The Probabilistic Method, 2nd Edition, Wiley, New York, 2000.

[5]

{5} D. Ben-Arieh, G. Gutin, M. Penn, A. Yeo, A. Zverovitch, Transformations of generalized ATSP into ATSP: experimental and theoretical study, Oper. Res. Lett. 41 (2003) 2581-2596.

[6]

{6} D. Berend, S.S. Skiena, Combinatorial dominance guarantees for heuristic algorithms, Manuscript, 2002.

[7]

{7} J. Bourgain, Walsh subspaces of lp product spaces, in: Séminaire d'analyse fonctionnelle, École Polytechnique, Centre de Mathématiques, 1979-80, pp. 41-49.

[8]

{8} C.S. Edwards, Some extremal properties of bipartite subgraphs, Canad. J. Math. 3 (1973) 475-485.

[9]

{9} C.S. Edwards, An improved lower bound for the number of edges in a largest bipartite subgraph, in: Proc. 2nd Czechoslovak Symposium on Graph Theory, Prague, 1975, pp. 167-181.

[10]

{10} P. Erdös, On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc. 51 (1945) 898-902.

[11]

{11} E. Friedgut, V. Rödl, Proof of a hypercontractive estimate via entropy, Israel J. Math. 125 (2001) 369-380.

[12]

{12} G. Grimmett, C. McDiarmid, On colouring random graphs, Math. Proc. Cambridge Philos. Soc. 77 (1975) 313-324.

[13]

{13} G. Gutin, A. Vainshtein, A. Yeo, Domination analysis of combinatorial optimization problems, Discrete Appl. Math. 29 (2003) 513-520.

[14]

{14} G. Gutin, A. Yeo, Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number, Discrete Appl. Math. 119 (2002) 107-116.

[15]

{15} G. Gutin, A. Yeo, Anti-matroids, Oper. Res. Lett. 30 (2002) 97-99.

[16]

{16} G. Gutin, A. Yeo, A. Zverovitch, Exponential neighborhoods and domination analysis for the TSP, in: G. Gutin, A.P. Punnen (Eds.), The Traveling Salesman Problem and Its Variations, Kluwer, Dordrecht, 2002.

[17]

{17} D.S. Johnson, G. Gutin, L. McGeoch, A. Yeo, X. Zhang, A. Zverovitch, Experimental analysis of heuristics for ATSP, in: G. Gutin, A.P. Punnen (Eds.), The Traveling Salesman Problem and Its Variations, Kluwer, Dordrecht, 2002.

[18]

{18} J. Håstad, S. Venkatesh, On the advantage over a random assignment, in: Annual ACM Symposium on Theory of Computing, 2002, pp. 43-52.

[19]

{19} A.E. Koller, S.D. Noble, Domination analysis of greedy heuristics for the frequency assignment problem, Discrete Math., in press.

[20]

{20} S. Poljak, V. Rödl, J. Spencer, Tournament ranking with expected profit in polynomial time, SIAM J. Discrete Math. 1 (1988) 372-376.

[21]

{21} A.P. Punnen, F. Margot, S.N. Kabadi, TSP heuristics: domination analysis and complexity, Algorithmica 35 (2003) 111-127.

[22]

{22} A.P. Punnen, S. Kabadi, Domination analysis of some heuristics for the asymmetric traveling salesman problem, Discrete Appl. Math. 119 (2002) 117-128.

[23]

{23} E. Sperner, Ein Satz über Untermegen einer endlichen Menge, Math. Z. 27 (1928) 544-548.

[24]

{24} M. Talagrand, On Russo's approximate 0-1-law, Ann. Prob. 22 (1994) 1376-1387.

Cited By

usti APunnen A(2017)Average value of solutions of the bipartite quadratic assignment problem and linkages to domination analysisOperations Research Letters10.1016/j.orl.2017.03.00445:3(232-237)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1016/j.orl.2017.03.004
ăźUstić ASokol VPunnen ABhattacharya B(2017)The bilinear assignment problemMathematical Programming: Series A and B10.1007/s10107-017-1111-1166:1-2(185-205)Online publication date: 1-Nov-2017
https://dl.acm.org/doi/10.1007/s10107-017-1111-1
Punnen ASripratak PKarapetyan D(2015)Average value of solutions for the bipartite boolean quadratic programs and rounding algorithmsTheoretical Computer Science10.1016/j.tcs.2014.11.008565:C(77-89)Online publication date: 2-Feb-2015
https://dl.acm.org/doi/10.1016/j.tcs.2014.11.008
Show More Cited By

Index Terms

Algorithms with large domination ratio
1. Mathematics of computing
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis

Recommendations

Domination analysis for minimum multiprocessor scheduling

Let P be a combinatorial optimization problem, and let A be an approximation algorithm for P. The domination ratio domr(A, s) is the maximal real q such that the solution x(I) obtained by A for any instance I of P of size s is not worse than at least ...
Cubic Graphs with Large Ratio of Independent Domination Number to Domination Number

A dominating set in a graph $$G$$G is a set $$S$$S of vertices such that every vertex outside $$S$$S has a neighbor in $$S$$S; the domination number$$\gamma (G)$$ (G) is the minimum size of such a set. The independent domination number, written $$i(G)$$...
An approximation algorithm for the partial vertex cover problem in hypergraphs

Let $$\mathcal {H}=(V,\mathcal {E})$$H=(V,E) be a hypergraph with set of vertices $$V, n:=|V|$$V,n:=|V| and set of (hyper-)edges $$\mathcal {E}, m:=|\mathcal {E}|$$E,m:=|E|. Let $$l$$l be the maximum size of an edge, $$\varDelta $$Δ be the maximum ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Algorithms

Journal of Algorithms Volume 50, Issue 1

January 2004

131 pages

ISSN:0196-6774

Issue’s Table of Contents

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 January 2004

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

usti APunnen A(2017)Average value of solutions of the bipartite quadratic assignment problem and linkages to domination analysisOperations Research Letters10.1016/j.orl.2017.03.00445:3(232-237)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1016/j.orl.2017.03.004
ăźUstić ASokol VPunnen ABhattacharya B(2017)The bilinear assignment problemMathematical Programming: Series A and B10.1007/s10107-017-1111-1166:1-2(185-205)Online publication date: 1-Nov-2017
https://dl.acm.org/doi/10.1007/s10107-017-1111-1
Punnen ASripratak PKarapetyan D(2015)Average value of solutions for the bipartite boolean quadratic programs and rounding algorithmsTheoretical Computer Science10.1016/j.tcs.2014.11.008565:C(77-89)Online publication date: 2-Feb-2015
https://dl.acm.org/doi/10.1016/j.tcs.2014.11.008
Crowston RFellows MGutin GJones MKim ERosamond FRuzsa IThomassé SYeo A(2014)Satisfying more than half of a system of linear equations over GF(2)Journal of Computer and System Sciences10.1016/j.jcss.2013.10.00280:4(687-696)Online publication date: 1-Jun-2014
https://dl.acm.org/doi/10.1016/j.jcss.2013.10.002
Punnen ASripratak PKarapetyan D(2013)Domination analysis of algorithms for bipartite boolean quadratic programsProceedings of the 19th international conference on Fundamentals of Computation Theory10.1007/978-3-642-40164-0_26(271-282)Online publication date: 19-Aug-2013
https://dl.acm.org/doi/10.1007/978-3-642-40164-0_26
Gutin GYeo A(2012)Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier widthDiscrete Applied Mathematics10.5555/2344966.2345139160:15(2323-2328)Online publication date: 1-Oct-2012
https://dl.acm.org/doi/10.5555/2344966.2345139
Gutin GYeo A(2012)Constraint satisfaction problems parameterized above or below tight boundsThe Multivariate Algorithmic Revolution and Beyond10.5555/2344236.2344252(257-286)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.5555/2344236.2344252
Lokshtanov DMisra NSaurabh S(2012)Kernelization --- preprocessing with a guaranteeThe Multivariate Algorithmic Revolution and Beyond10.5555/2344236.2344248(129-161)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.5555/2344236.2344248
Gutin GKim ESzeider SYeo A(2011)A probabilistic approach to problems parameterized above or below tight boundsJournal of Computer and System Sciences10.1016/j.jcss.2010.06.00177:2(422-429)Online publication date: 1-Mar-2011
https://dl.acm.org/doi/10.1016/j.jcss.2010.06.001
Alon NGutin GKim ESzeider SYeo ACharikar M(2010)Solving MAX-r-SAT above a tight lower boundProceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithms10.5555/1873601.1873645(511-517)Online publication date: 17-Jan-2010
https://dl.acm.org/doi/10.5555/1873601.1873645
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents