Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Approximating a solution of the s-t max-cut problem with a deterministic annealing algorithm.

C Dang1

  • 1Department of Manufacturing Engineering and Engineering Management, City University of Hong Kong, Kowloon, People's Republic of China. mecdang@cityu.edu.hk

Neural Networks : the Official Journal of the International Neural Network Society
|January 11, 2001
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

[Analysis of current status in the construction of stroke centers and the quality of ischemic stroke medical care in Guangdong province (2023-2024)].

Zhonghua yi xue za zhi·2025
Same author

Energy deposition in liquid scintillators composed of CsPbBr<sub>3</sub> colloidal nanocrystal dispersions.

Nanoscale·2024
Same author

Biomarkers and Cognition Study, Singapore (BIOCIS): Protocol, Study Design, and Preliminary Findings.

The journal of prevention of Alzheimer's disease·2024
Same author

RUNX1-activated upregulation of lncRNA RNCR3 promotes cell proliferation, invasion, and suppresses apoptosis in colorectal cancer via miR-1301-3p/AKT1 axis in vitro and in vivo.

Clinical & translational oncology : official publication of the Federation of Spanish Oncology Societies and of the National Cancer Institute of Mexico·2020
Same author

Network change in the ipsilesional cerebellum is correlated with motor recovery following unilateral pontine infarction.

European journal of neurology·2019
Same author

Prospective evaluation of the cardiac safety of HER2-targeted therapies in patients with HER2-positive breast cancer and compromised heart function: the SAFE-HEaRt study.

Breast cancer research and treatment·2019

This study introduces an efficient algorithm for the NP-hard s-t max-cut problem. The method formulates a continuous optimization problem and uses a logarithmic barrier function for approximation.

Area of Science:

  • Combinatorial Optimization
  • Continuous Optimization
  • Numerical Analysis

Background:

  • The s-t max-cut problem is a computationally challenging NP-hard problem.
  • Existing methods for solving this problem often face scalability and efficiency limitations.
  • Approximation algorithms are crucial for finding near-optimal solutions to NP-hard problems.

Purpose of the Study:

  • To formulate an equivalent linearly constrained continuous optimization problem for the s-t max-cut problem.
  • To propose a novel algorithm for approximating the solution to this continuous problem.
  • To analyze the convergence properties and efficiency of the proposed algorithm.

Main Methods:

  • Formulation of an equivalent continuous optimization problem with linear constraints.

Related Experiment Videos

  • Application of a logarithmic barrier function with a decreasing barrier parameter (annealing).
  • Utilizing a feasible descent direction with step lengths between zero and one.

    • Main Results:

    • The algorithm guarantees that lower and upper bounds are automatically satisfied.
    • Convergence to at least a local minimum is proven under specific conditions.
    • Numerical results indicate the algorithm is effective and efficient for approximating s-t max-cut solutions.

    Conclusions:

    • The proposed algorithm offers a viable approach for approximating solutions to the NP-hard s-t max-cut problem.
    • The logarithmic barrier method with annealing provides a robust framework for this optimization task.
    • The algorithm demonstrates practical effectiveness and efficiency in numerical experiments.