Search Results - subject:"NP-complete problems"

Optimizing the resource consumption of Blockchain technology in business systems

Juričić, Vedran; Radošević, Matea; Fuzul, Ena - In: Business systems research : a system view accross … 11 (2020) 3, pp. 78-92

research is to provide different insights into blockchain technology and to propose NP-complete problems as a suitable … cryptocurrencies but focusing on incorporating NP-complete problems as a secondary, more useful option. Results Using the properties of … NP-complete problems, it is possible to solve various problems in different areas, such as science, biology, medicine and …

Persistent link: https://www.econbiz.de/10012414439

Optimizing the resource consumption of Blockchain technology in business systems

Juričić, Vedran; Radošević, Matea; Fuzul, Ena - In: Business Systems Research (BSR) 11 (2020) 3, pp. 78-92

Persistent link: https://www.econbiz.de/10015408743

Numerical experiments with LP formulations of the maximum clique problem

Kardos, Dóra; Patassy, Patrik; Szabó, Sándor; … - In: Central European journal of operations research 30 (2022) 4, pp. 1353-1367

Persistent link: https://www.econbiz.de/10013445722

A clique search problem and its application to machine scheduling

Szabó, Sándor - In: Operations research forum 2 (2021) 4, pp. 1-12

Persistent link: https://www.econbiz.de/10012794437

A generalized constructive algorithm using insertion-based

Danilovic, Milos; Ilic, Oliver - In: Computers & operations research : and their … 66 (2016), pp. 29-43

Persistent link: https://www.econbiz.de/10011428984

Chapter 14. The Complexity of Computing Equilibria

Papadimitriou, Christos - In: Handbook of game theory with economic applications : …, (pp. 779-810). 2015

In one of the most influential existence theorems in mathematics, John F. Nash proved in 1950 that any normal form game has an equilibrium. More than five decades later, it was shown that the computational task of finding such an equilibrium is intractable, that is, unlikely to be carried out...

Persistent link: https://www.econbiz.de/10014025445

The complexitiy of computing equilibria

Papadimitriou, Christos H. - 2015

Persistent link: https://www.econbiz.de/10011498318

Optimal redistricting under geographical constraints: Why "pack and crack" does not work

Puppe, Clemens; Tasnádi, Attila - In: Economics Letters 105 (2009) 1, pp. 93-96

We show that optimal partisan redistricting with geographical constraints is a computationally intractable (NP-complete) problem. In particular, even when voter's preferences are deterministic, a solution is generally not obtained by concentrating opponent's supporters in "unwinnable" districts...

Persistent link: https://www.econbiz.de/10005023457

Phase transitions of subset sum and Shannon's limit in source coding

Sasamoto, Tomohiro - In: Physica A: Statistical Mechanics and its Applications 321 (2003) 1, pp. 369-374

We consider statistical properties of an NP-complete problem, the subset sum, using the methods and concepts of statistical mechanics. After introducing the statistical mechanical treatment of the problem, the phase transition behaviors are discussed. We also introduce a source coding scheme...

Persistent link: https://www.econbiz.de/10010873773

Almost All Graphs of Degree 4 are 3-colorable

Achlioptas, Dimitris; Moore, Cristopher - Santa Fe Institute - 2001

The technique of approximating the mean path of Markov chains by differential equations has proved to be a useful tool in analyzing the performance of heuristics on random graph instances. However, only a small family of algorithms can currently be analyzed by this method, due to the need to...

Persistent link: https://www.econbiz.de/10005739919