DOI: 10.1007/3-540-45411-x_16. Critical Parallelization of Local Search for MAX-SAT

Critical Parallelization of Local Search for MAX-SAT

10.1007/3-540-45411-x_16

Crossref book-chapter

Springer Berlin Heidelberg

Lecture Notes in Computer Science (297)

Bibliography

Roli, A., & Blum, C. (2001). Critical Parallelization of Local Search for MAX-SAT. AI*IA 2001: Advances in Artificial Intelligence, 147â158.

Authors 2

Andrea Roli (first)
Christian Blum (additional)

References 22 Referenced 3

Roberto Battiti and Marco Protasi. Reactive Search, a history-base heuristic for MAX-SAT. ACM Journal of Experimental Algorithmics, 1997. (10.1145/264216.264220)
Patrice Calegari, Giovanni Coray, Alain Hertz, Daniel Kobler, and Pierre Kuonen. A taxonomy of evolutionary algorithms in combinatorial optimization. Journal of Heuristics, 5:145–158, 1999. (10.1023/A:1009625526657) / Journal of Heuristics by P. Calegari (1999)
David Corne, Marco Dorigo, and Fred Glover, editors. New Ideas in Optimization. Advanced topics in computer science series. McGraw-Hill, 1999.
Frank-Michael Dittes. Optimization on rugged landscapes: A new general purpose Monte Carlo approach. Physical Review Letters, 76(25):4651–4655, June 1996. (10.1103/PhysRevLett.76.4651) / Physical Review Letters by F.-M. Dittes (1996)
Marco Dorigo and Gianni Di Caro. The Ant Colony Optimization meta-heuristic. In D. Corne, M. Dorigo, and F. Glover, editors, New Ideas in Optimization, pages 11–32. McGraw-Hill, 1999. Also available as Technical Report IRIDIA/99-1, Universit é Libre de Bruxelles, Belgium. / New Ideas in Optimization / Technical Report by M. Dorigo (1999)
Michael R. Garey and David S. Johnson. Computers and intractability; a guide to the theory of NP-completeness. W.H. Freeman, 1979.
Fred Glover and Manuel Laguna. Tabu Search. Kluwer Academic Publichers, 1997. (10.1007/978-1-4615-6089-0)
Pierre Hansen and Nenad Mladenovic. An introduction to Variable Neighborhood Search. In Stefan Voss, Silvano Martello, Ibrahim Osman, and Catherine Roucairol, editors, Meta-heuristics: advances and trends in local search paradigms for optimization, chapter 30, pages 433–458. Kluwer Academic Publishers, 1999. (10.1007/978-1-4615-5775-3_30)
Stuart A. Kauffman. The origins of order. Oxford University Press, New York, 1993. / The origins of order by S. A. Kauffman (1993)
Stuart A. Kauffman. At home in the universe. Oxford Press, 1995.
Stuart A. Kauffman and William Macready. Technological evolution and adaptive organizations. Complexity, 26(2):26–43, March 1995. (10.1002/cplx.6130010208) / Complexity by S. A. Kauffman (1995)
S. Kirkpartick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 13 May 1983, 220(4598):671–680, 1983. (10.1126/science.220.4598.671) / Science by S. Kirkpartick (1983)
William G. Macready, Athanassios G. Siapas, and Stuart A. Kauffman. Criticality and parallelism in combinatorial optimization. Science, 271:56–59, January 1996. (10.1126/science.271.5245.56) / Science by W. G. Macready (1996)
David McAllester, Bart Selman, and Henry Kautz. Evidence for invariants in local search. In Proceedings of the 14th National Conference on Artificial Intelligence and 9th Innovative Applications of Artificial Intelligence Conference (AAAI-97/IAAI-97), pages 321–326, Menlo Park, July 27–31 1997. AAAI Press.
Patrick Mills and Edward Tsang. Guided Local Search for solving SAT and weighted MAX-SAT Problems. In Ian Gent, Hans van Maaren, and Toby Walsh, editors, SAT2000, pages 89–106. IOS Press, 2000.
David G. Mitchell, Bart Selman, and Hector J. Levesque. Hard and easy distributions of sat problems. In Proceedings, Tenth National Conference on Artificial Intelligence, pages 459–465. AAAI Press/MIT Press, July 1992.
P. Moscato. Memetic algorithms: A short introduction. In F. Glover D. Corne and M. Dorigo, editors, New Ideas in Optimization. McGraw-Hill, 1999.
Andrea Roli. Criticality and parallelism in GSAT. In Henry Kautz and Bart Selman, editors, Electronic Notes in Discrete Mathematics, volume 9. Elsevier Science Publishers, 2001. (10.1016/S1571-0653(04)00319-1)
Bart Selman, Hector J. Levesque, and David G. Mitchell. A new method for solving hard satisfiability problems. In Paul Rosenbloom and Peter Szolovits, editors, Proceedings of the Tenth National Conference on Artificial Intelligence, pages 440–446, Menlo Park, California, 1992. American Association for Artificial Intelligence, AAAI Press.
Thomas Stützle. Local Search Algorithms for Combinatorial Problems-Analysis, Algorithms and New Applications. DISKI-Dissertationen zur Künstliken Intelligenz. infix, 1999.
Stefan Voss, Silvano Martello, Ibrahim H. Osman, and Catherine Roucairol, editors. Meta-Heuristics-Advances and Trends in Local Search Paradigms for Optimization. Kluwer Academic Publishers, 1999. (10.1007/978-1-4615-5775-3)
Benjamin W. Wah and Yi Shang. Discrete Lagrangian-Based Search for Solving MAX-SAT Problems. In Proc. 15th Int’l Joint Conf. on Artificial Intelligence, IJCAI, pages 378–383, Aug. 1997.

Dates

Type	When
Created	18 years, 1 month ago (July 16, 2007, 8:17 a.m.)
Deposited	6 years, 4 months ago (April 30, 2019, 7:26 p.m.)
Indexed	1 year ago (Sept. 4, 2024, 6:04 p.m.)
Issued	24 years, 8 months ago (Jan. 1, 2001)
Published	24 years, 8 months ago (Jan. 1, 2001)
Published Online	23 years, 11 months ago (Sept. 7, 2001)
Published Print	24 years, 8 months ago (Jan. 1, 2001)

Funders 0

None

BibTeX

@inbook{Roli_2001, title={Critical Parallelization of Local Search for MAX-SAT}, ISBN={9783540454113}, ISSN={0302-9743}, url={http://dx.doi.org/10.1007/3-540-45411-x_16}, DOI={10.1007/3-540-45411-x_16}, booktitle={AI*IA 2001: Advances in Artificial Intelligence}, publisher={Springer Berlin Heidelberg}, author={Roli, Andrea and Blum, Christian}, year={2001}, pages={147–158} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2024,
        9,
        4
      ]
    ],
    "date-time": "2024-09-04T22:04:12Z",
    "timestamp": 1725487452411
  },
  "publisher-location": "Berlin, Heidelberg",
  "reference-count": 22,
  "publisher": "Springer Berlin Heidelberg",
  "isbn-type": [
    {
      "type": "print",
      "value": "9783540426011"
    },
    {
      "type": "electronic",
      "value": "9783540454113"
    }
  ],
  "content-domain": {
    "domain": [],
    "crossmark-restriction": false
  },
  "published-print": {
    "date-parts": [
      [
        2001
      ]
    ]
  },
  "DOI": "10.1007/3-540-45411-x_16",
  "type": "book-chapter",
  "created": {
    "date-parts": [
      [
        2007,
        7,
        16
      ]
    ],
    "date-time": "2007-07-16T12:17:28Z",
    "timestamp": 1184588248000
  },
  "page": "147-158",
  "source": "Crossref",
  "is-referenced-by-count": 3,
  "title": "Critical Parallelization of Local Search for MAX-SAT",
  "prefix": "10.1007",
  "author": [
    {
      "given": "Andrea",
      "family": "Roli",
      "sequence": "first",
      "affiliation": []
    },
    {
      "given": "Christian",
      "family": "Blum",
      "sequence": "additional",
      "affiliation": []
    }
  ],
  "member": "297",
  "published-online": {
    "date-parts": [
      [
        2001,
        9,
        7
      ]
    ]
  },
  "reference": [
    {
      "key": "16_CR1",
      "doi-asserted-by": "crossref",
      "unstructured": "Roberto Battiti and Marco Protasi. Reactive Search, a history-base heuristic for MAX-SAT. ACM Journal of Experimental Algorithmics, 1997.",
      "DOI": "10.1145/264216.264220"
    },
    {
      "key": "16_CR2",
      "doi-asserted-by": "publisher",
      "first-page": "145",
      "DOI": "10.1023/A:1009625526657",
      "volume": "5",
      "author": "P. Calegari",
      "year": "1999",
      "unstructured": "Patrice Calegari, Giovanni Coray, Alain Hertz, Daniel Kobler, and Pierre Kuonen. A taxonomy of evolutionary algorithms in combinatorial optimization. Journal of Heuristics, 5:145\u2013158, 1999.",
      "journal-title": "Journal of Heuristics"
    },
    {
      "key": "16_CR3",
      "unstructured": "David Corne, Marco Dorigo, and Fred Glover, editors. New Ideas in Optimization. Advanced topics in computer science series. McGraw-Hill, 1999."
    },
    {
      "issue": "25",
      "key": "16_CR4",
      "doi-asserted-by": "publisher",
      "first-page": "4651",
      "DOI": "10.1103/PhysRevLett.76.4651",
      "volume": "76",
      "author": "F.-M. Dittes",
      "year": "1996",
      "unstructured": "Frank-Michael Dittes. Optimization on rugged landscapes: A new general purpose Monte Carlo approach. Physical Review Letters, 76(25):4651\u20134655, June 1996.",
      "journal-title": "Physical Review Letters"
    },
    {
      "key": "16_CR5",
      "series-title": "Technical Report",
      "first-page": "11",
      "volume-title": "New Ideas in Optimization",
      "author": "M. Dorigo",
      "year": "1999",
      "unstructured": "Marco Dorigo and Gianni Di Caro. The Ant Colony Optimization meta-heuristic. In D. Corne, M. Dorigo, and F. Glover, editors, New Ideas in Optimization, pages 11\u201332. McGraw-Hill, 1999. Also available as Technical Report IRIDIA/99-1, Universit \u00e9 Libre de Bruxelles, Belgium."
    },
    {
      "key": "16_CR6",
      "unstructured": "Michael R. Garey and David S. Johnson. Computers and intractability; a guide to the theory of NP-completeness. W.H. Freeman, 1979."
    },
    {
      "key": "16_CR7",
      "doi-asserted-by": "crossref",
      "unstructured": "Fred Glover and Manuel Laguna. Tabu Search. Kluwer Academic Publichers, 1997.",
      "DOI": "10.1007/978-1-4615-6089-0"
    },
    {
      "key": "16_CR8",
      "doi-asserted-by": "crossref",
      "unstructured": "Pierre Hansen and Nenad Mladenovic. An introduction to Variable Neighborhood Search. In Stefan Voss, Silvano Martello, Ibrahim Osman, and Catherine Roucairol, editors, Meta-heuristics: advances and trends in local search paradigms for optimization, chapter 30, pages 433\u2013458. Kluwer Academic Publishers, 1999.",
      "DOI": "10.1007/978-1-4615-5775-3_30"
    },
    {
      "key": "16_CR9",
      "volume-title": "The origins of order",
      "author": "S. A. Kauffman",
      "year": "1993",
      "unstructured": "Stuart A. Kauffman. The origins of order. Oxford University Press, New York, 1993."
    },
    {
      "key": "16_CR10",
      "unstructured": "Stuart A. Kauffman. At home in the universe. Oxford Press, 1995."
    },
    {
      "issue": "2",
      "key": "16_CR11",
      "doi-asserted-by": "crossref",
      "first-page": "26",
      "DOI": "10.1002/cplx.6130010208",
      "volume": "26",
      "author": "S. A. Kauffman",
      "year": "1995",
      "unstructured": "Stuart A. Kauffman and William Macready. Technological evolution and adaptive organizations. Complexity, 26(2):26\u201343, March 1995.",
      "journal-title": "Complexity"
    },
    {
      "issue": "4598",
      "key": "16_CR12",
      "doi-asserted-by": "publisher",
      "first-page": "671",
      "DOI": "10.1126/science.220.4598.671",
      "volume": "220",
      "author": "S. Kirkpartick",
      "year": "1983",
      "unstructured": "S. Kirkpartick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 13 May 1983, 220(4598):671\u2013680, 1983.",
      "journal-title": "Science"
    },
    {
      "key": "16_CR13",
      "doi-asserted-by": "publisher",
      "first-page": "56",
      "DOI": "10.1126/science.271.5245.56",
      "volume": "271",
      "author": "W. G. Macready",
      "year": "1996",
      "unstructured": "William G. Macready, Athanassios G. Siapas, and Stuart A. Kauffman. Criticality and parallelism in combinatorial optimization. Science, 271:56\u201359, January 1996.",
      "journal-title": "Science"
    },
    {
      "key": "16_CR14",
      "unstructured": "David McAllester, Bart Selman, and Henry Kautz. Evidence for invariants in local search. In Proceedings of the 14th National Conference on Artificial Intelligence and 9th Innovative Applications of Artificial Intelligence Conference (AAAI-97/IAAI-97), pages 321\u2013326, Menlo Park, July 27\u201331 1997. AAAI Press."
    },
    {
      "key": "16_CR15",
      "unstructured": "Patrick Mills and Edward Tsang. Guided Local Search for solving SAT and weighted MAX-SAT Problems. In Ian Gent, Hans van Maaren, and Toby Walsh, editors, SAT2000, pages 89\u2013106. IOS Press, 2000."
    },
    {
      "key": "16_CR16",
      "unstructured": "David G. Mitchell, Bart Selman, and Hector J. Levesque. Hard and easy distributions of sat problems. In Proceedings, Tenth National Conference on Artificial Intelligence, pages 459\u2013465. AAAI Press/MIT Press, July 1992."
    },
    {
      "key": "16_CR17",
      "unstructured": "P. Moscato. Memetic algorithms: A short introduction. In F. Glover D. Corne and M. Dorigo, editors, New Ideas in Optimization. McGraw-Hill, 1999."
    },
    {
      "key": "16_CR18",
      "doi-asserted-by": "crossref",
      "unstructured": "Andrea Roli. Criticality and parallelism in GSAT. In Henry Kautz and Bart Selman, editors, Electronic Notes in Discrete Mathematics, volume 9. Elsevier Science Publishers, 2001.",
      "DOI": "10.1016/S1571-0653(04)00319-1"
    },
    {
      "key": "16_CR19",
      "unstructured": "Bart Selman, Hector J. Levesque, and David G. Mitchell. A new method for solving hard satisfiability problems. In Paul Rosenbloom and Peter Szolovits, editors, Proceedings of the Tenth National Conference on Artificial Intelligence, pages 440\u2013446, Menlo Park, California, 1992. American Association for Artificial Intelligence, AAAI Press."
    },
    {
      "key": "16_CR20",
      "unstructured": "Thomas St\u00fctzle. Local Search Algorithms for Combinatorial Problems-Analysis, Algorithms and New Applications. DISKI-Dissertationen zur K\u00fcnstliken Intelligenz. infix, 1999."
    },
    {
      "key": "16_CR21",
      "doi-asserted-by": "crossref",
      "unstructured": "Stefan Voss, Silvano Martello, Ibrahim H. Osman, and Catherine Roucairol, editors. Meta-Heuristics-Advances and Trends in Local Search Paradigms for Optimization. Kluwer Academic Publishers, 1999.",
      "DOI": "10.1007/978-1-4615-5775-3"
    },
    {
      "key": "16_CR22",
      "unstructured": "Benjamin W. Wah and Yi Shang. Discrete Lagrangian-Based Search for Solving MAX-SAT Problems. In Proc. 15th Int\u2019l Joint Conf. on Artificial Intelligence, IJCAI, pages 378\u2013383, Aug. 1997."
    }
  ],
  "container-title": "Lecture Notes in Computer Science",
  "original-title": [],
  "link": [
    {
      "URL": "http://link.springer.com/content/pdf/10.1007/3-540-45411-X_16",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2019,
        4,
        30
      ]
    ],
    "date-time": "2019-04-30T23:26:43Z",
    "timestamp": 1556666803000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "http://link.springer.com/10.1007/3-540-45411-X_16"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        2001
      ]
    ]
  },
  "ISBN": [
    "9783540426011",
    "9783540454113"
  ],
  "references-count": 22,
  "URL": "http://dx.doi.org/10.1007/3-540-45411-X_16",
  "relation": {},
  "ISSN": [
    "0302-9743"
  ],
  "subject": [],
  "published": {
    "date-parts": [
      [
        2001
      ]
    ]
  }
}