Integer equal flows
The integer equal flow problem is an NP-hard network flow problem, in which all arcs in given sets R1,…,R[subscript ℓ] must carry equal flow. We show that this problem is effectively inapproximable, even if the cardinality of each set R[subscript k] is two. When ℓ is fixed, it is solvable in polynom...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Elsevier Science
2010
|
| Online Access: | http://hdl.handle.net/1721.1/54777 https://orcid.org/0000-0002-9595-459X |
| _version_ | 1811089005599522816 |
|---|---|
| author | Meyers, Carol A. Schulz, Andreas S. |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Meyers, Carol A. Schulz, Andreas S. |
| author_sort | Meyers, Carol A. |
| collection | MIT |
| description | The integer equal flow problem is an NP-hard network flow problem, in which all arcs in given sets R1,…,R[subscript ℓ] must carry equal flow. We show that this problem is effectively inapproximable, even if the cardinality of each set R[subscript k] is two. When ℓ is fixed, it is solvable in polynomial time. |
| first_indexed | 2024-09-23T14:12:20Z |
| format | Article |
| id | mit-1721.1/54777 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:12:20Z |
| publishDate | 2010 |
| publisher | Elsevier Science |
| record_format | dspace |
| spelling | mit-1721.1/547772022-10-01T19:44:31Z Integer equal flows Meyers, Carol A. Schulz, Andreas S. Sloan School of Management Schulz, Andreas S. Schulz, Andreas S. The integer equal flow problem is an NP-hard network flow problem, in which all arcs in given sets R1,…,R[subscript ℓ] must carry equal flow. We show that this problem is effectively inapproximable, even if the cardinality of each set R[subscript k] is two. When ℓ is fixed, it is solvable in polynomial time. 2010-05-12T20:20:09Z 2010-05-12T20:20:09Z 2009-03 2008-08 Article http://purl.org/eprint/type/SubmittedJournalArticle http://hdl.handle.net/1721.1/54777 Meyers, Carol A., and Andreas S. Schulz. “Integer equal flows.” Operations Research Letters 37.4 (2009): 245-249. © 2009 Elsevier B.V. https://orcid.org/0000-0002-9595-459X en_US http://dx.doi.org/10.1016/j.orl.2009.03.006 Operations Research Letters Attribution-Noncommercial-Share Alike 3.0 Unported http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Elsevier Science Andreas Schulz |
| spellingShingle | Meyers, Carol A. Schulz, Andreas S. Integer equal flows |
| title | Integer equal flows |
| title_full | Integer equal flows |
| title_fullStr | Integer equal flows |
| title_full_unstemmed | Integer equal flows |
| title_short | Integer equal flows |
| title_sort | integer equal flows |
| url | http://hdl.handle.net/1721.1/54777 https://orcid.org/0000-0002-9595-459X |
| work_keys_str_mv | AT meyerscarola integerequalflows AT schulzandreass integerequalflows |