Minimum Link Flow Problem and Its Solution With Sparse Modeling
Recently, a statistical modeling approach called sparse modeling has attracted much attention, especially in the fields of signal and image processing. Sparse modeling is applicable to solve problems in a variety of fields, and a few applications have begun to be explored in the field of information...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2025-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/11115035/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849390398354489344 |
|---|---|
| author | Ryotaro Matsuo Ryo Nakamura Hiroyuki Ohsaki |
| author_facet | Ryotaro Matsuo Ryo Nakamura Hiroyuki Ohsaki |
| author_sort | Ryotaro Matsuo |
| collection | DOAJ |
| description | Recently, a statistical modeling approach called sparse modeling has attracted much attention, especially in the fields of signal and image processing. Sparse modeling is applicable to solve problems in a variety of fields, and a few applications have begun to be explored in the field of information networking. Sparse modeling is expected to be applicable to many information networking problems, but it has not yet been well investigated. In this study, we examine how sparse modeling can be applied to solve a new network flow problem called minimum link flow problem. The minimum link flow problem, which includes problems such as the minimum cost flow problem and the minimum Steiner tree problem under certain conditions, is a combinatorial optimization problem, and to the best of our knowledge, no effective solution has been proposed for the minimum link flow problem. In this study, we formulate the minimum link flow problem using sparse modeling and propose a greedy algorithm called Constrained Orthogonal Matching Pursuit (COMP), which imposes both upper and lower bounds on the solution. Through various experiments, we investigate how effectively the COMP can solve the minimum link flow problem. Our findings include that COMP can solve the minimum link flow problem with multiple sources and sinks 1.1–1.3 times more effectively than benchmark conventional methods. |
| format | Article |
| id | doaj-art-036a9d03602c4effadb1ffeb0fad6a24 |
| institution | Kabale University |
| issn | 2169-3536 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj-art-036a9d03602c4effadb1ffeb0fad6a242025-08-20T03:41:40ZengIEEEIEEE Access2169-35362025-01-011313947913948910.1109/ACCESS.2025.359626711115035Minimum Link Flow Problem and Its Solution With Sparse ModelingRyotaro Matsuo0https://orcid.org/0000-0002-6394-1655Ryo Nakamura1https://orcid.org/0000-0002-5453-6869Hiroyuki Ohsaki2Faculty of Engineering, Fukuoka University, Fukuoka, JapanFaculty of Engineering, Fukuoka University, Fukuoka, JapanDepartment of Informatics, Graduate School of Science and Technology, Kwansei Gakuin University, Sanda, Hyogo, JapanRecently, a statistical modeling approach called sparse modeling has attracted much attention, especially in the fields of signal and image processing. Sparse modeling is applicable to solve problems in a variety of fields, and a few applications have begun to be explored in the field of information networking. Sparse modeling is expected to be applicable to many information networking problems, but it has not yet been well investigated. In this study, we examine how sparse modeling can be applied to solve a new network flow problem called minimum link flow problem. The minimum link flow problem, which includes problems such as the minimum cost flow problem and the minimum Steiner tree problem under certain conditions, is a combinatorial optimization problem, and to the best of our knowledge, no effective solution has been proposed for the minimum link flow problem. In this study, we formulate the minimum link flow problem using sparse modeling and propose a greedy algorithm called Constrained Orthogonal Matching Pursuit (COMP), which imposes both upper and lower bounds on the solution. Through various experiments, we investigate how effectively the COMP can solve the minimum link flow problem. Our findings include that COMP can solve the minimum link flow problem with multiple sources and sinks 1.1–1.3 times more effectively than benchmark conventional methods.https://ieeexplore.ieee.org/document/11115035/Constrained orthogonal matching pursuit (COMP)minimum link flow problemnetwork floworthogonal matching pursuit (OMP)sparse modeling |
| spellingShingle | Ryotaro Matsuo Ryo Nakamura Hiroyuki Ohsaki Minimum Link Flow Problem and Its Solution With Sparse Modeling IEEE Access Constrained orthogonal matching pursuit (COMP) minimum link flow problem network flow orthogonal matching pursuit (OMP) sparse modeling |
| title | Minimum Link Flow Problem and Its Solution With Sparse Modeling |
| title_full | Minimum Link Flow Problem and Its Solution With Sparse Modeling |
| title_fullStr | Minimum Link Flow Problem and Its Solution With Sparse Modeling |
| title_full_unstemmed | Minimum Link Flow Problem and Its Solution With Sparse Modeling |
| title_short | Minimum Link Flow Problem and Its Solution With Sparse Modeling |
| title_sort | minimum link flow problem and its solution with sparse modeling |
| topic | Constrained orthogonal matching pursuit (COMP) minimum link flow problem network flow orthogonal matching pursuit (OMP) sparse modeling |
| url | https://ieeexplore.ieee.org/document/11115035/ |
| work_keys_str_mv | AT ryotaromatsuo minimumlinkflowproblemanditssolutionwithsparsemodeling AT ryonakamura minimumlinkflowproblemanditssolutionwithsparsemodeling AT hiroyukiohsaki minimumlinkflowproblemanditssolutionwithsparsemodeling |