STRUCTCOMB, “Structure and computational difficulty in combinatorial optimization: an interdisciplinary approach” contract
- CNCS IDEI Grant PN-II-ID-PCE-2011-3-0981
- Principal investigator: Gabriel Istrate.
- Starting date: May 1st 2012.
- Duration: until
April 30 2015. April 30 2016.December 31, 2016
- Project proposal and objectives
- (Martie 2012, in romanian): Institutul e-Austria angajeaza cercetatori stiintifici (postdoctorali) in matematica-informatică in cadrul proiectului PN-II-ID-PCE-2011-3-0981 “Structure and computational difficulty in combinatorial optimization: an interdisciplinary approach” (data limita: 30 Aprilie 2012)
- (March 2012, IN ENGLISH): Hiring ads: ANCS and Euraxess (only valid until April 30, 2012)
- Reports (tar.gz.archive)
collaborating with Eva Kaslik and Mircea Marin.
- Programs to generate (hard to solve) instances of satisfiability/ILP based on Kneser and Schrijver’s theorems. (Note: SAT instances are in DIMACS-CNF format; for ILP solving one needs GUROBI)
- Cosmin Bonchis, Gabriel Istrate. Improved Approximation Algorithms for Low-Density Instances of the Minimum Entropy Set Cover Problem. Information Processing Letters, Volume 114, Issue 7, July 2014.
- Gabriel Istrate, Adrian Crăciun “Proof Complexity and the Lovasz-Kneser Theorem Proceedings of the 17th International Conference on Theory and Applications of Satisfiability Testing, SAT 2014 vol. 8561 , pp. 138-153. Lecture Notes in Computer Science, Springer Verlag, 2014.
- Gabriel Istrate, Mircea Marin Learning cover context-free grammars from structural data Proceedings of ICTAC 2014 Volume 8687, pp 241-258, Lecture Notes in Computer Science, Springer Verlag, 2014.
- Gabriel Istrate. Identifying almost-sorted permutations from TCP buffer dynamics. Scientific Annals of Computer Science, XXV (1), pp. 133-154, 2015.
- Gabriel Istrate. Reachability and Recurrence in a Modular Generalization of Annihilating Random Walks (and lights-out games) to hypergraphs. Theoretical Computer Science, 580, pp. 83-93, 2015. 2015.
- Gabriel Istrate, Cosmin Bonchiș. Partition into heapable sequences, heap tableaux and a multiset extension of Hammersley’s process. Proceedings of CPM 2015, Lecture Notes in Computer Science 9133, pp. 261-271. Springer Verlag, 2015.
- James Aisenberg, Maria-Luisa Bonet, Samuel Buss, Adrian Crăciun, Gabriel Istrate, Short Proofs for the Kneser -Lovasz Coloring Principle, Proceedings of ICALP 2015, Lecture Notes in Computer Science vol. 9135, pp. 44-55. 2015.
- Journal version of previous paper, Information and Computation special issue dedicated to ICALP 2015 (to appear)
- Gabriel Istrate, Cosmin Bonchiș and Liviu P. Dinu. The Minimum Entropy Submodular Set Cover Problem. Proceedings of LATA 2016 , Lecture Notes in Computer Science, Springer Verlag.
- Zoltan Neda, Larissa Davidova, Szerena Ujvari, Gabriel Istrate, Gambler’s ruin problem on Erdos-Renyi graphs, Elsevier, Physica A: Statistical Mechanics and its Applications, 468, pp. 157-167 (2017).
- Gabriel Istrate, Cosmin Bonchiș Heapability, interactive particle systems, partial orders: results and open problems. Proceedings of the 18th International Conference on Descriptive Complexity of Formal Systems (DCFS’2016), Lecture Notes in Computer Science, vol. 9777, p.18-28, Springer Verlag, 2016.
Essentially completed papers, under (re)submission.
- Gabriel Istrate, Cosmin Bonchiș and Mircea Marin “Interactive Particle Systems, Explosive Random Walks on Hypergraphs and the WalkSAT algorithm.“. Presented at DCM 2014. Revised version (linked above) due for Random Structures and Algorithms.
- Gabriel Istrate “Threshold properties for stopping times“ due for, Applicable Analysis and Discrete Mathematics.
- Gabriel Istrate, Cosmin Bonchiș “Worst-case fairness in TU-cooperative games: A parametric approach”. Due for International Journal of Game Theory.
Manuscripts in progress
- Gabriel Istrate, Cosmin Bonchiș, Parameterized complexity of computing power indices in cooperative skill games with agent failures.
- Gabriel Istrate, Predrag Janičić. ” Locating phase transition in mixture models of constraint satisfaction problems”.
- Gabriel Istrate, Cosmin Bonchiș. Hammersley’s process with multiple lifelines and a conjecture on decomposing permutations into heapable sequences.
- Janos Balogh, Cosmin Bonchis, Diana Dinis Gabriel Istrate (title in progress).
- Gabriel Istrate, Adrian Crăciun, Cosmin Bonchiş “Topological obstructions to the colorability of gain graphs“
- Gabriel Istrate, Adrian Crăciun “Parameterized inverse Satisfiability”
- Gabriel Istrate, Cosmin Bonchiş, Mircea Marin “On the Curvature of Submodular Functions and the Approximability of Minimum Entropy Submodular Set Cover”
- Gabriel Istrate, Cosmin Bonchis “A greedy approach to low entropy couplings”.
- Cosmin Bonchiş, Gabriel Istrate “Minimum entropy solutions to assignment problems”
- Gabriel Istrate, “An accessibility relation on polymatroids and minimum entropy optimization”