#### 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
December 31, 2016**April 30 2015**.**April 30 2016**.

### Documents

- 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)

### Team

- Gabriel Istrate.
- Adrian Crãciun
- Cosmin Bonchiş.

collaborating with Eva Kaslik and Mircea Marin.

### Deliverables

- 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)

### Papers

- 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”