Publications of Groups G4 and G5 (since January 2005)

Books or Book Chapters

1. G. Calinescu and C.G. Fernandes, Maximum Planar Subgraph, Chapter R43 in Approximation Algorithms and Metaheuristics, Teofilo F. Gonzalez (Ed.), Francis and Taylor, 1 ed. Boca Raton: Chapman and Hall/CRC Press, 2007, v. 10, p. 1-1434.

Publications in Journals

1. M. Baiou and J.R. Correa, The node edge-weighted 2-edge-connected subgraph problem: Linear relaxation, facets and separation, Discrete Optimization, 3 (2006), 123--135.
2. N. Bansal, J.R. Correa, C. Kenyon, and M. Sviridenko, Bin packing in multiple dimensions: inapproximability results and approximation schemes. Math. Oper. Res. 31 (2006), no. 1, 31--49.
3. E. G. Birgin, J.M. Martínez, W. F. Mascarenhas and D. P. Ronconi, Method of sentinels for packing items whitin arbitrary convex regions, Journal of the Operational Research Society 57, pp. 735--746, 2006.
4. E. G. Birgin, J.M. Martínez, F. H. Nishihara and D. P. Ronconi, Orthogonal packing of rectangular items within arbitrary convex regions by nonlinear optimization, Computers & Operations Research 33, pp. 3535--3548, 2006.
5. E. G. Birgin, J.M. Martínez and D. P. Ronconi, Optimizing the packing of cylinders into a rectangular container: a nonlinear approach, European Journal of Operational Research 160 (2005), 19--33.
6. E. G. Birgin and F.N. C. Sobral, Minimizing the object dimensions in circle and sphere packing problems, Computers & Operations Research (Elsevier Science) (34): 2589-2603, 2007. http://dx.doi.org/10.1016/j.cor.2005.10.001
7. E. G. Birgin, R. Morabito and F.H. Nishihara, A note on an L-approach for solving the manufacturer's pallet loading problem, Journal of the Operational Research Society 56, pp. 1448--1451, 2005.
8. E. C. Bracht, L. A. A. Meira and F.K. Miyazawa. A greedy approximation algorithm for the uniform labeling problem, ACM Journal on Experimental Algorithm, 10(2):1-18, 2005.
9. F. Chataigner, L.R.B. Salgado and Y. Wakabayashi, Approximability and inapproximability of problems on balanced connected partitions of graphs, Discrete Mathematics and Theoretical Computer Science (DMTCS) (electronic), vol.9, 2007, 177-192.
10. G. Cintra, F.K. Miyazawa, Y. Wakabayashi, E. C. Xavier, A note on the approximability of cutting stock problems. European Journal on Operations Research, Volume 183, Issue 3 (2007), Pages 1328-1332; DOI:http://dx.doi.org/10.1016/j.ejor.2005.09.053
11. G. Cintra, F. K. Miyazawa, Y. Wakabayashi, E. C. Xavier. Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming, European Journal on Operations Research, to appear; DOI: http://dx.doi.org/10.1016/j.ejor.2007.08.007
12. J.R. Correa, Resource augmentation in two-dimensional packing with orthogonal rotations, Oper. Res. Lett. 34 (2006), no. 1, 85-93.
13. J.R. Correa, S. Fiorini and N.E. Stier-Moses, A note on the precedence-constrained class sequencing problem, Discrete Appl. Math. 155 (2007), no. 3, 257--259.
14. J.R. Correa, M.X. Goemans, Improved bounds on nonblocking 3-stage Clos networks, SIAM J. Comput. 37 (2007), no. 3, 870--894 (electronic).
15. J.R. Correa and A. Schulz, Single-machine scheduling with precedence constraints, Math. Oper. Res. 30 (2005), no. 4, 1005-1021.
16. J.R. Correa, A.S. Schulz and N.E. Stier-Moses, Fast, fair, and efficient flows in networks. Oper. Res. 55 (2007), no. 2, 215--225.
17. P. Feofiloff, C.G. Fernandes, C.E. Ferreira, and J.C. de Pina, A Note on Johnson, Minkoff and Phillips' Algorithm for the Prize-Collecting Steiner Tree Problem, Information Processing Letters , 103 (2007), no. 5, 195--202.
18. C.G. Fernandes, V. Lacroix and M.-F. Sagot, Reaction motifs in metabolic networks, IEEE/ACM Transactions on Computational Biology and Bioinformatics, Vol. 3, No. 4, pp. 360-368, 2006.
19. C.G. Fernandes, O. Lee, and Y. Wakabayashi, Minimum cycle cover and the Chinese postman problems on mixed graphs with bounded tree width, Discrete Applied Mathematics, to appear.
20. G. Manic and Y. Wakabayashi, Packing triangles in low degree graphs and indifference graphs, Discrete Mathematics, Volume 308 (2008) Issue 8, 1455-1471; DOI:http://dx.doi.org/10.1016/j.disc.2007.07.100.
21. F.V. Martinez, J.C. de Pina, and J.A.R. Soares. Algorithms for terminal Steiner trees. Theoretical Computer Science, v. 389, p. 133-142, 2007.
22. F.K. Miyazawa and Y. Wakabayashi, Two- and three-dimensional parametric packing problems, Computers and Operations Research,(Elsevier Science) (34): 2589-2603, 2007;DOI: http://dx.doi.org/10.1016/j.cor.2005.10.001
23. E.M. Rodrigues, M.-F. Sagot and Y. Wakabayashi, The maximum agreement forest problem: approximation algorithms and computational experiments, Theoretical Computer Science, 374 (2007) 91--110.
24. E.C. Xavier and F.K. Miyazawa, Approximation schemes for knapsack problems with shelf divisions, Theoretical Computer Science, (Elsevier Science) (352): 71--84, 2006; DOI: http://dx.doi.org/10.1016/j.tcs.2005.10.036
25. E.C. Xavier and F.K. Miyazawa, A One-Dimensional Bin Packing Problem with Shelf Divisions, Discrete Applied Mathematics, to appear; DOI: http://dx.doi.org/10.1016/j.dam.2007.05.053
26. E. C. Xavier and F. K. Miyazawa, The Class Constrained Bin Packing Problem with Applications to Video-on-Demand. Theoretical Computer Science, to appear; DOI: http://dx.doi.org/10.1016/j.tcs.2008.01.001

Publications in International Conference Proceedings

1. S. Adi, M.D.V. Braga, C.G. Fernandes, C.E. Ferreira, F.H.V. Martinez, M.-F Sagot, M.A. Stefanes, C. Tjandraatmadja and Y. Wakabayashi, Repetition-free longest common subsequence, accepted to LAGOS 2007 (IV Latin-American Algorithms, Graphs and Optimization Symposium).
2. M. Baļou and J.R. Correa, The node-edge weighted 2-edge connected subgraph problem: linear relaxation, facets and separation, Proceedings of the Second Brazilian Symposium on Graphs, Algorithms and Combinatorics (GRACO 2005), Electronic Notes in Discrete Mathematics 19 (2005), 103-109.
3. D. M. Batista, N. L. S. da Fonseca, F. K. Miyazawa. A set of schedulers for grid networks. 22nd ACM Symposium on Applied Computing (ACM-SAC 2007), pp. 209-213, 2007.
4. C.F. Bornstein, E.S. Laber and M.A.F. Más, On Behalf the Seller and Society: a Bicriteria Mechanism for Unit-Demand Auctions, Proceedings of the LATIN 2006: 7th Latin American Symposium of Theoretical Informatics, Lecture Notes in Computer Science. 3887 (2006), 211-233.
5. F. Chataigner, G. Manic, Y.Wakabayashi and R. Yuster, Approximation algorithms and hardness results for the clique packing problem, Eurocomb 2007, European Conference on Combinatorics, Graph Theory and Applications, Electronic Notes in Discrete Mathematics Volume 29, Pages 397-401, 2007; URL of ENDM http://www.sciencedirect.com/science/journal/1571065
6. R. Cominetti, J.R.Correa and N.E. Stier-Moses, Network games with atomic players, in: Automata, languages and programming Part I, 525--536, Lecture Notes in Comput. Sci., 4051, Springer, Berlin, 2006.
7. J.R. Correa and M.R. Wagner, LP-based online scheduling: from single to parallel machines, IPCO (Integer programming and combinatorial optimization), 196--209, Lecture Notes in Comput. Sci., 3509, Springer, Berlin, 2005.
8. J.R. Correa, A.S. Schulz and N.E. Stier-Moses, On the inefficiency of equilibria in congestion games (extended abstract), IPCO (Integer programming and combinatorial optimization), 167--181, Lecture Notes in Comput. Sci., 3509, Springer, Berlin, 2005.
9. J.R. Correa, C.G. Fernandes, M. Matamala and Y. Wakabayashi, A 5/3-approximation for finding spanning trees with many leaves in cubic graphs, WAOA 2007 (5th Workshop on Approximation and Online Algorithms). Lecture Notes in Computer Science, v. 4927 (2008), p. 184-192.
10. J.R. Correa, C.G. Fernandes and Y. Wakabayashi, Approximating rational objectives is as easy as approximating linear ones, Proceedings of SWAT 2006 (10th Scandinavian Workshop on Algorithm Theory), Lecture Notes in Computer Science, vol. 4059 (2006), pp. 351--362.
11. C.G. Fernandes, V. Lacroix, and M.-F. Sagot, Reaction motifs in metabolic networks, Proceedings of the Workshop on Algorithms in Bioinformatics (Eivissa, Spain, WABI 2005), Lecture Notes in Computer Science, vol. 3692 (2006), 178-191.
12. G. Manic and Y. Wakabayashi, Packing triangles in low degree graphs and indifference graphs, European Conference on Combinatorics, Graph Theory, and Applications (EUROCOMB 2005), Berlin, Germany, September 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science (DMTCS), Vol. AE 2005, pp. 251--256.
13. F.V. Martinez, J.C. de Pina, and J. Soares, Algorithms for terminal Steiner trees, Proceedings of the 11th Annual International Computing and Combinatorics Conference COCOON 2005, Kunming, China, August 16--29, 2005, Lecture Notes in Computer Science, Vol. 3595, pp. 369--379, Springer-Verlag, 2005.
14. L.A.A. Meira and F. K. Miyazawa. A continuous facility location problem and its application to a clustering problem. 23rd ACM Symposium on Applied Computing (ACM-SAC 2008), pp. 1830--1835, 2008.
15. F.K. Miyazawa and Y. Wakabayashi, Two- and three-dimensional parametric packing problems. Proceedings of the Second Brazilian Symposium on Graphs, Algorithms and Combinatorics (GRACO 2005). Electronic Notes in Discrete Mathematics, 19:313--319, 2005.
16. E.C. Xavier and F.K. Miyazawa, A One-dimensional bin packing problem with shelf divisions. Proceedings of the Second Brazilian Symposium on Graphs, Algorithms and Combinatorics (GRACO 2005). Electronic Notes in Discrete Mathematics 19:329--335, 2005.
17. E.C. Xavier and F.K. Miyazawa, The class constrained bin packing problem with applications to video-on-demand, Proceedings of the 12th Annual International Computing and Combinatorics Conference COCOON 2006, Lecture Notes in Computer Sciences , Vol. 4112, pp. 439--448, Springer-Verlag, 2006.

Editorial Work

1. C. Choffrut, and Y. Wakabayashi (editors) Preface [Imre Simon, the tropical computer scientist].Theor. Inform. Appl. 39 (2005), no. 1, i-vii.
2. P. Feofiloff, C.M.H.de Figueiredo and Y. Wakabayashi (editors) Preface [Proceedings of the Second Brazilian Symposium on Graphs, Algorithms and Combinatorics]. Electronic Notes in Discrete Mathematics, (Elsevier Science Publishers) 19, 1-7, 2005.

Submitted Manuscripts

1. D. Batista, N. L. S. da Fonseca, F.K. Miyazawa and F. Granelli. Self-Adjustment of Resource Allocation for Grid Applications
2. F. Chataigner, G. Manic, Y.Wakabayashi and R. Yuster, Approximation algorithms and hardness results for the clique packing problem, 2007.
3. J. R. Correa, C.G. Fernandes and Y. Wakabayashi, Approximating a class of combinatorial problems with rational objective function, 2006.
4. W. F. Mascarenhas and E.G. Birgin, Using sentinels to detect intersections, 2006.
5. L. A. A. Meira and F. K. Miyazawa. Semidefinite Programming Based Algorithms for the Sparsest Cut Problem.
6. F. K. Miyazawa and Y. Wakabayashi. Three-dimensional Packings with Rotations.
7. E. C. Xavier and F. K. Miyazawa. A Note on Dual Approximation Algorithms for Class Constrained Bin Packing Problems.