Document

APPROX

**Published in:** LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

Coflow is a set of related parallel data flows in a network. The goal of the coflow scheduling is to process all the demands of the given coflows while minimizing the weighted completion time. It is known that the coflow scheduling problem admits several polynomial-time 5-approximation algorithms that compute solutions by rounding linear programming (LP) relaxations of the problem. In this paper, we investigate the time-indexed LP relaxation for coflow scheduling. We show that the integrality gap of the time-indexed LP relaxation is at most 4. We also show that yet another polynomial-time 5-approximation algorithm can be obtained by rounding the solutions to the time-indexed LP relaxation.

Takuro Fukunaga. Integrality Gap of Time-Indexed Linear Programming Relaxation for Coflow Scheduling. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 36:1-36:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fukunaga:LIPIcs.APPROX/RANDOM.2022.36, author = {Fukunaga, Takuro}, title = {{Integrality Gap of Time-Indexed Linear Programming Relaxation for Coflow Scheduling}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {36:1--36:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.36}, URN = {urn:nbn:de:0030-drops-171581}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.36}, annote = {Keywords: coflow scheduling, hypergraph matching, approximation algorithm} }

Document

**Published in:** LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

We consider a network design problem called the generalized terminal backup problem. Whereas earlier work investigated the edge-connectivity constraints only, we consider both edge- and node-connectivity constraints for this problem. A major contribution of this paper is
the development of a strongly polynomial-time 4/3-approximation algorithm for the problem. Specifically, we show that a linear programming relaxation of the problem is half-integral, and that the half-integral optimal solution can be rounded to a 4/3-approximate solution. We also prove that the linear programming relaxation of the problem with the edge-connectivity constraints is equivalent to minimizing the cost of half-integral multiflows that satisfy flow demands given from terminals. This observation implies a strongly polynomial-time algorithm for computing a minimum cost half-integral multiflow under flow demand constraints.

Takuro Fukunaga. Approximating the Generalized Terminal Backup Problem via Half-integral Multiflow Relaxation. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 316-328, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{fukunaga:LIPIcs.STACS.2015.316, author = {Fukunaga, Takuro}, title = {{Approximating the Generalized Terminal Backup Problem via Half-integral Multiflow Relaxation}}, booktitle = {32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)}, pages = {316--328}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-78-1}, ISSN = {1868-8969}, year = {2015}, volume = {30}, editor = {Mayr, Ernst W. and Ollinger, Nicolas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.316}, URN = {urn:nbn:de:0030-drops-49236}, doi = {10.4230/LIPIcs.STACS.2015.316}, annote = {Keywords: survivable network design, multiflow, LP rounding} }

Document

**Published in:** LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

The inventory routing problem involves trading off inventory holding
costs at client locations with vehicle routing costs to deliver
frequently from a single central depot to meet deterministic client demands over a finite planing horizon. In this paper, we consider periodic solutions that visit clients in one of several specified frequencies, and focus on the case when the frequencies of visiting nodes are nested. We give the first constant-factor approximation algorithms for designing optimum nested periodic schedules for the problem with no limit on vehicle capacities by simple reductions to prize-collecting network design problems. For instance, we present a 2.55-approximation algorithm for the minimum-cost nested periodic
schedule where the vehicle routes are modeled as minimum Steiner trees. We also show a general reduction from the capacitated
problem where all vehicles have the same capacity to the uncapacitated
version with a slight loss in performance. This reduction gives a
4.55-approximation for the capacitated problem. In addition, we prove several structural results relating the values of optimal policies of various types.

Takuro Fukunaga, Afshin Nikzad, and R. Ravi. Deliver or hold: Approximation Algorithms for the Periodic Inventory Routing Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 209-225, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{fukunaga_et_al:LIPIcs.APPROX-RANDOM.2014.209, author = {Fukunaga, Takuro and Nikzad, Afshin and Ravi, R.}, title = {{Deliver or hold: Approximation Algorithms for the Periodic Inventory Routing Problem}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)}, pages = {209--225}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-74-3}, ISSN = {1868-8969}, year = {2014}, volume = {28}, editor = {Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.209}, URN = {urn:nbn:de:0030-drops-46985}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.209}, annote = {Keywords: Inventry Routing Problem, Approximation algorithm, Prize-collecting Steiner Tree} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail