Search results for "PLS-complete"

Found 17 publication records. Showing 17 according to the selection in the facets

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
59	Philippe Chapdelaine, Nadia Creignou	The complexity of Boolean constraint satisfaction local search problems.	Ann. Math. Artif. Intell.	2005	DBLP DOI BibTeX RDF	PLS-complete, optimization, complexity, local search, satisfiability, PLS
56	Alexander Skopalik, Berthold Vöcking	Inapproximability of pure nash equilibria.	STOC	2008	DBLP DOI BibTeX RDF	approximation, local search, congestion games
29	Anand Bhalgat, Tanmoy Chakraborty 0001, Sanjeev Khanna	Approximating pure nash equilibrium in cut, party affiliation, and satisfiability games.	EC	2010	DBLP DOI BibTeX RDF	cut games, party affiliation games, potential games, pure nash equilibrium, approximation algorithms
29	Juliane Dunkel, Andreas S. Schulz	On the Complexity of Pure-Strategy Nash Equilibria in Congestion and Local-Effect Games.	WINE	2006	DBLP DOI BibTeX RDF
29	Sophie Fischer, Leen Torenvliet	The Malleability of TSP_{2Opt}.	WG	1995	DBLP DOI BibTeX RDF
27	James B. Orlin, Abraham P. Punnen, Andreas S. Schulz	Integer Programming: Optimization and Evaluation Are Equivalent.	WADS	2009	DBLP DOI BibTeX RDF
27	Heiner Ackermann, Heiko Röglin, Berthold Vöcking	On the impact of combinatorial structure on congestion games.	J. ACM	2008	DBLP DOI BibTeX RDF	convergence, local search, Nash equilibria, Congestion games
27	Heiner Ackermann, Heiko Röglin, Berthold Vöcking	On the Impact of Combinatorial Structure on Congestion Games.	FOCS	2006	DBLP DOI BibTeX RDF
24	Tobias Tscheuschner	The local max-cut problem is PLS-complete even on graphs with maximum degree five	CoRR	2010	DBLP BibTeX RDF
24	Dominic Dumrauf, Burkhard Monien, Karsten Tiemann	MultiProcessor Scheduling is PLS-Complete.	HICSS	2009	DBLP DOI BibTeX RDF
17	Heiner Ackermann, Alexander Skopalik	On the Complexity of Pure Nash Equilibria in Player-Specific Network Congestion Games.	WINE	2007	DBLP DOI BibTeX RDF
17	Felix Brandt 0001, Felix A. Fischer, Markus Holzer 0001	Symmetries and the Complexity of Pure Nash Equilibrium.	STACS	2007	DBLP DOI BibTeX RDF
14	Tanmoy Chakraborty 0001, Sanjeev Khanna	Nash Dynamics in Constant Player and Bounded Jump Congestion Games.	SAGT	2009	DBLP DOI BibTeX RDF
14	Xin Ai 0002, Vikram Srinivasan, Chen-Khong Tham	Optimality and Complexity of Pure Nash Equilibria in the Coverage Game.	IEEE J. Sel. Areas Commun.	2008	DBLP DOI BibTeX RDF
14	Andreas Emil Feldmann, Heiko Röglin, Berthold Vöcking	Computing Approximate Nash Equilibria in Network Congestion Games.	SIROCCO	2008	DBLP DOI BibTeX RDF
14	Steve Chien, Alistair Sinclair	Convergence to approximate Nash equilibria in congestion games.	SODA	2007	DBLP BibTeX RDF
14	Alex Fabrikant, Christos H. Papadimitriou, Kunal Talwar	The complexity of pure Nash equilibria.	STOC	2004	DBLP DOI BibTeX RDF	PLS-completeness, pure Nash equilibria, complexity, games, local search, congestion games, PLS