Search results for "max-cut"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
19	Ai-Fan Ling, Cheng-Xian Xu, Feng-Min Xu	A discrete filled function algorithm embedded with continuous approximation for solving max-cut problems.	Eur. J. Oper. Res.	2009	DBLP DOI BibTeX RDF
19	Frauke Liers, G. Pardella	A Simple MAX-CUT Algorithm for Planar Graphs.	CTW	2009	DBLP BibTeX RDF
19	Laurent Gourvès, Jérôme Monnot	On Strong Equilibria in the Max Cut Game.	WINE	2009	DBLP DOI BibTeX RDF
19	Alantha Newman	Max Cut.	Encyclopedia of Algorithms	2008	DBLP DOI BibTeX RDF
19	Andrzej Dudek, Vojtech Rödl	Finding Folkman Numbers via MAX CUT Problem.	Electron. Notes Discret. Math.	2008	DBLP DOI BibTeX RDF
19	Cristina Bazgan, Zsolt Tuza	Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3.	J. Discrete Algorithms	2008	DBLP DOI BibTeX RDF
19	Luca Trevisan	Max Cut and the Smallest Eigenvalue	CoRR	2008	DBLP BibTeX RDF
19	Petros Drineas, Ravi Kannan, Michael W. Mahoney	Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms.	Random Struct. Algorithms	2008	DBLP DOI BibTeX RDF
19	Claire Mathieu, Warren Schudy	Yet another algorithm for dense max cut: go greedy.	SODA	2008	DBLP BibTeX RDF
19	Sera Kahruman-Anderoglu, Elif Kolotoglu, Sergiy Butenko, Illya V. Hicks	On greedy construction heuristics for the MAX-CUT problem.	Int. J. Comput. Sci. Eng.	2007	DBLP DOI BibTeX RDF
19	Federico Della Croce, Marcin Jakub Kaminski, Vangelis Th. Paschos	An exact algorithm for MAX-CUT in sparse graphs.	Oper. Res. Lett.	2007	DBLP DOI BibTeX RDF
19	Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell	Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?.	SIAM J. Comput.	2007	DBLP DOI BibTeX RDF
19	Giulia Galbiati, Francesco Maffioli	Approximating Max Cut with Limited Unbalance.	Electron. Notes Discret. Math.	2006	DBLP DOI BibTeX RDF
19	Jiahai Wang	An improved discrete Hopfield neural network for Max-Cut problems.	Neurocomputing	2006	DBLP DOI BibTeX RDF
19	Wenceslas Fernandez de la Vega, Marek Karpinski	On the Sample Complexity of MAX-CUT.	Electron. Colloquium Comput. Complex.	2006	DBLP BibTeX RDF
19	Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani	Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut.	Electron. Colloquium Comput. Complex.	2006	DBLP BibTeX RDF
19	Wenceslas Fernandez de la Vega, Marek Karpinski	Approximation Complexity of Nondense Instances of MAX-CUT.	Electron. Colloquium Comput. Complex.	2006	DBLP BibTeX RDF
19	Eric Angel, Evripidis Bampis, Laurent Gourvès	Approximation algorithms for the bi-criteria weighted MAX-CUT problem.	Discret. Appl. Math.	2006	DBLP DOI BibTeX RDF
19	Carsten Thomassen	On the max-cut problem for a planar, cubic, triangle-free graph, and the Chinese postman problem for a planar triangulation.	J. Graph Theory	2006	DBLP DOI BibTeX RDF
19	Guy Kindler, Ryan O'Donnell, Subhash Khot, Elchanan Mossel	Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?	Electron. Colloquium Comput. Complex.	2005	DBLP BibTeX RDF
19	Hernán Alperin, Ivo Nowak	Lagrangian Smoothing Heuristics for Max-Cut.	J. Heuristics	2005	DBLP DOI BibTeX RDF	non-convex programming, approximation methods and heuristics, pathfollowing, combinatorial optimization, semidefinite programming, quadratic programming
19	Béla Bollobás, Alex D. Scott	Max Cut for Random Graphs with a Planted Partition.	Comb. Probab. Comput.	2004	DBLP DOI BibTeX RDF
19	Eran Halperin, Dror Livnat, Uri Zwick	MAX CUT in cubic graphs.	J. Algorithms	2004	DBLP DOI BibTeX RDF
19	Monique Laurent	Semidefinite Relaxations for Max-Cut.	The Sharpest Cut	2004	DBLP DOI BibTeX RDF
19	S. Thomas McCormick, M. R. Rao, Giovanni Rinaldi	Easy and difficult objective functions for max cut.	Math. Program.	2003	DBLP DOI BibTeX RDF
19	David Avis, Jun Umemoto	Stronger linear programming relaxations of max-cut.	Math. Program.	2003	DBLP DOI BibTeX RDF
19	Paola Festa, Panos M. Pardalos, Mauricio G. C. Resende, Celso C. Ribeiro	Randomized heuristics for the Max-Cut problem.	Optim. Methods Softw.	2002	DBLP DOI BibTeX RDF
19	Monique Laurent	Tighter Linear and Semidefinite Relaxations for Max-Cut Based on the Lov[a-acute]sz--Schrijver Lift-and-Project Procedure.	SIAM J. Optim.	2002	DBLP DOI BibTeX RDF
19	Samuel Burer, Renato D. C. Monteiro, Yin Zhang 0010	Rank-Two Relaxation Heuristics for MAX-CUT and Other Binary Quadratic Programs.	SIAM J. Optim.	2002	DBLP DOI BibTeX RDF
19	Tiziana Calamoneri, Irene Finocchi, Yannis Manoussakis, Rossella Petreschi	On max cut in cubic graphs.	Parallel Algorithms Appl.	2002	DBLP DOI BibTeX RDF
19	Wenceslas Fernandez de la Vega, Marek Karpinski	A Polynomial Time Approximation Scheme for Subdense MAX-CUT	Electron. Colloquium Comput. Complex.	2002	DBLP BibTeX RDF
19	Miguel F. Anjos, Henry Wolkowicz	Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem.	Discret. Appl. Math.	2002	DBLP DOI BibTeX RDF
19	Uriel Feige, Gideon Schechtman	On the optimality of the random hyperplane rounding technique for MAX CUT.	Random Struct. Algorithms	2002	DBLP DOI BibTeX RDF
19	Uriel Feige, Marek Karpinski, Michael Langberg	Improved approximation of Max-Cut on graphs of bounded degree.	J. Algorithms	2002	DBLP DOI BibTeX RDF
19	Miguel F. Anjos, Henry Wolkowicz	Geometry of Semidefinite Max-Cut Relaxations via Matrix Ranks.	J. Comb. Optim.	2002	DBLP DOI BibTeX RDF
19	Wenceslas Fernandez de la Vega, Claire Kenyon	A Randomized Approximation Scheme for Metric MAX-CUT.	J. Comput. Syst. Sci.	2001	DBLP DOI BibTeX RDF
19	Anna Galluccio, Martin Loebl, Jan Vondrák	Optimization via enumeration: a new algorithm for the Max Cut Problem.	Math. Program.	2001	DBLP DOI BibTeX RDF
19	John E. Mitchell 0001	Restarting after Branching in the SDP Approach to MAX-CUT and Similar Combinatorial Optimization Problems.	J. Comb. Optim.	2001	DBLP DOI BibTeX RDF
19	Chris H. Q. Ding, Xiaofeng He, Hongyuan Zha, Ming Gu 0002, Horst D. Simon	A Min-max Cut Algorithm for Graph Partitioning and Data Clustering.	ICDM	2001	DBLP DOI BibTeX RDF
19	Amir Beck, Marc Teboulle	A probabilistic result for the max-cut problem on random graphs.	Oper. Res. Lett.	2000	DBLP DOI BibTeX RDF
19	Uriel Feige, Marek Karpinski, Michael Langberg	Improved Approximation of MAX-CUT on Graphs of Bounded Degree	Electron. Colloquium Comput. Complex.	2000	DBLP BibTeX RDF
19	Wenceslas Fernandez de la Vega, Marek Karpinski	Polynomial time approximation of dense weighted instances of MAX-CUT.	Random Struct. Algorithms	2000	DBLP DOI BibTeX RDF
19	Chuangyin Dang	Approximating a solution of the s-t max-cut problem with a deterministic annealing algorithm.	Neural Networks	2000	DBLP DOI BibTeX RDF
19	Hans L. Bodlaender, Ton Kloks, Rolf Niedermeier	SIMPLE MAX-CUT for unit interval graphs and graphs with few P4s.	Electron. Notes Discret. Math.	1999	DBLP DOI BibTeX RDF
19	Howard J. Karloff	How Good is the Goemans-Williamson MAX CUT Algorithm?	SIAM J. Comput.	1999	DBLP DOI BibTeX RDF
19	Alexander A. Ageev, Maxim Sviridenko	Approximation Algorithms for Maximum Coverage and Max Cut with Given Sizes of Parts.	IPCO	1999	DBLP DOI BibTeX RDF
19	Tiziana Calamoneri, Irene Finocchi, Yannis Manoussakis, Rossella Petreschi	A Parallel Approximation Algorithm for the Max Cut Problem on Cubic Graphs.	ASIAN	1999	DBLP DOI BibTeX RDF
19	Uriel Feige	Randomized Rounding for Semidefinite Programs-Variations on the MAX CUT Example.	RANDOM-APPROX	1999	DBLP DOI BibTeX RDF
19	Uri Zwick	Outward Rotations: A Tool for Rounding Solutions of Semidefinite Programming Relaxations, with Applications to MAX CUT and Other Problems.	STOC	1999	DBLP DOI BibTeX RDF
19	Wenceslas Fernandez de la Vega, Marek Karpinski	Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT	Electron. Colloquium Comput. Complex.	1998	DBLP BibTeX RDF
19	Magnús M. Halldórsson, Hoong Chuin Lau	Low-degree Graph Partitioning via Local Search with Applications to Constraint Satisfaction, Max Cut, and Coloring.	J. Graph Algorithms Appl.	1997	DBLP DOI BibTeX RDF
19	Monique Laurent, Svatopluk Poljak, Franz Rendl	Connections between semidefinite relaxations of the max-cut and stable set problems.	Math. Program.	1997	DBLP DOI BibTeX RDF
19	Nobuo Funabiki, Junji Kitamichi, Seishi Nishikawa	An evolutionary neural network algorithm for max cut problems.	ICNN	1997	DBLP DOI BibTeX RDF
19	Jaroslav Nesetril, Daniel Turzík	Solving and Approximating Combinatorial Optimization Problems (Towards MAX CUT and TSP).	SOFSEM	1997	DBLP DOI BibTeX RDF
19	Wenceslas Fernandez de la Vega	MAX-CUT has a randomized approximation scheme in dense graphs.	Random Struct. Algorithms	1996	DBLP DOI BibTeX RDF
19	Howard J. Karloff	How Good is the Goemans-Williamson MAX CUT Algorithm?	STOC	1996	DBLP DOI BibTeX RDF
19	Philip N. Klein, Hsueh-I Lu	Efficient Approximation Algorithms for Semidefinite Programs Arising from MAX CUT and COLORING.	STOC	1996	DBLP DOI BibTeX RDF
19	Svatopluk Poljak, Franz Rendl	Solving the Max-cut Problem Using Eigenvalues.	Discret. Appl. Math.	1995	DBLP DOI BibTeX RDF
19	Monique Laurent, Svatopluk Poljak	One-third-integrality in the max-cut problem.	Math. Program.	1995	DBLP DOI BibTeX RDF
19	Svatopluk Poljak	Integer Linear Programs and Local Search for Max-Cut.	SIAM J. Comput.	1995	DBLP DOI BibTeX RDF
19	Svatopluk Poljak, Zsolt Tuza	The expected relative error of the polyhedral approximation of the max-cut problem.	Oper. Res. Lett.	1994	DBLP DOI BibTeX RDF
19	Svatopluk Poljak, Franz Rendl	Node and edge relaxations of the Max-cut problem.	Computing	1994	DBLP DOI BibTeX RDF
19	Nguyen Van Ngoc, Zsolt Tuza	Linear-Time Algorithms for the Max Cut Problem.	Comb. Probab. Comput.	1993	DBLP DOI BibTeX RDF
19	Charles Delorme, Svatopluk Poljak	Combinatorial Properties and the Complexity of a Max-cut Approximation .	Eur. J. Comb.	1993	DBLP DOI BibTeX RDF
19	Charles Delorme, Svatopluk Poljak	The performance of an eigenvalue bound on the max-cut problem in some classes of graphs.	Discret. Math.	1993	DBLP DOI BibTeX RDF
19	Svatopluk Poljak, Daniel Turzík	Max-cut in circulant graphs.	Discret. Math.	1992	DBLP DOI BibTeX RDF
19	Endre Boros, Peter L. Hammer	The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds.	Ann. Oper. Res.	1991	DBLP DOI BibTeX RDF
19	Christoph Hohmann, Walter Kern	Optimization and optimality test for the Max-Cut Problem.	ZOR Methods Model. Oper. Res.	1990	DBLP DOI BibTeX RDF
19	Vasek Chvátal, C. Ebenegger	A note on line digraphs and the directed max-cut problem.	Discret. Appl. Math.	1990	DBLP DOI BibTeX RDF
19	Francisco Barahona	Planar Multicommodity Flows, Max Cut, and the Chinese Postman Problem.	Polyhedral Combinatorics	1990	DBLP DOI BibTeX RDF
19	Martin Grötschel, George L. Nemhauser	A polynomial algorithm for the max-cut problem on graphs without long odd cycles.	Math. Program.	1984	DBLP DOI BibTeX RDF
19	Martin Grötschel, William R. Pulleyblank	Weakly bipartite graphs and the Max-cut problem.	Oper. Res. Lett.	1981	DBLP DOI BibTeX RDF
16	Kamalika Chaudhuri, Eran Halperin, Satish Rao, Shuheng Zhou	A rigorous analysis of population stratification with limited data.	SODA	2007	DBLP BibTeX RDF
16	Johan Håstad	On Nontrivial Approximation of CSPs.	APPROX-RANDOM	2006	DBLP DOI BibTeX RDF
16	Amin Coja-Oghlan, Andreas Goerdt, André Lanka, Frank Schädlich	Certifying Unsatisfiability of Random 2k-SAT Formulas Using Approximation Techniques.	FCT	2003	DBLP DOI BibTeX RDF
16	Uri Zwick	Semidefinite Programming Based Approximation Algorithms.	FSTTCS	2001	DBLP DOI BibTeX RDF
16	David R. Karger, Rajeev Motwani 0001, Madhu Sudan 0001	Approximate Graph Coloring by Semidefinite Programming.	J. ACM	1998	DBLP DOI BibTeX RDF	approximation algorithms, NP-completeness, randomized algorithms, graph coloring, chromatic number
16	Pierluigi Crescenzi, Luca Trevisan	On Approximation Scheme Preserving Reducability and Its Applications.	FSTTCS	1994	DBLP DOI BibTeX RDF
15	Adam N. Letchford, Michael Malmros Sørensen	Binary Positive Semidefinite Matrices and Associated Integer Polytopes.	IPCO	2008	DBLP DOI BibTeX RDF	semidefinite programming, Polyhedral combinatorics
15	Iannis Tourlakis	New Lower Bounds for Vertex Cover in the Lovasz-Schrijver Hierarchy.	CCC	2006	DBLP DOI BibTeX RDF
15	Subhash Khot	On the Unique Games Conjecture.	FOCS	2005	DBLP DOI BibTeX RDF
11	Mohsen Bayati, David Gamarnik, Prasad Tetali	Combinatorial approach to the interpolation method and scaling limits in sparse random graphs.	STOC	2010	DBLP DOI BibTeX RDF	scaling limit, constraint satisfaction problems, random graphs, partition function
11	Ariel Kulik, Hadas Shachnai, Tami Tamir	Maximizing submodular set functions subject to multiple linear constraints.	SODA	2009	DBLP DOI BibTeX RDF
11	Neeldhara Misra, Venkatesh Raman 0001, Saket Saurabh 0001, Somnath Sikdar	The Budgeted Unique Coverage Problem and Color-Coding.	CSR	2009	DBLP DOI BibTeX RDF
11	Jon Lee 0001, Vahab S. Mirrokni, Viswanath Nagarajan, Maxim Sviridenko	Non-monotone submodular maximization under matroid and knapsack constraints.	STOC	2009	DBLP DOI BibTeX RDF	approximation algorithms, matroids, knapsacks, submodular functions
11	Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao 0001, Oded Regev 0001, David Steurer	Rounding Parallel Repetitions of Unique Games.	FOCS	2008	DBLP DOI BibTeX RDF
11	Hannes Moser, Venkatesh Raman 0001, Somnath Sikdar	The Parameterized Complexity of the Unique Coverage Problem.	ISAAC	2007	DBLP DOI BibTeX RDF
11	Uriel Feige, Vahab S. Mirrokni, Jan Vondrák	Maximizing Non-Monotone Submodular Functions.	FOCS	2007	DBLP DOI BibTeX RDF
11	Gareth E. Evans, Jonathan M. Keith, Dirk P. Kroese	Parallel cross-entropy optimization.	WSC	2007	DBLP DOI BibTeX RDF
11	Marco Carpentieri	On the BMDGAs and Neural Nets.	FOCI	2007	DBLP DOI BibTeX RDF
11	Anupam Gupta 0001, Kunal Talwar	Approximating unique games.	SODA	2006	DBLP DOI BibTeX RDF
11	Erik D. Demaine, Mohammad Taghi Hajiaghayi, Uriel Feige, Mohammad R. Salavatipour	Combination can be hard: approximability of the unique coverage problem.	SODA	2006	DBLP DOI BibTeX RDF
11	Marco Carpentieri, Vito Fedullo	A genetic model based on simulated crossover of quaternary genes for quadratic fitness.	GECCO	2006	DBLP DOI BibTeX RDF	marginal distribution genetic algorithms
11	Qihui Zhu, Jianbo Shi	Shape from Shading: Recognizing the Mountains through a Global View.	CVPR (2)	2006	DBLP DOI BibTeX RDF
11	Moses Charikar, Konstantin Makarychev, Yury Makarychev	Near-optimal algorithms for unique games.	STOC	2006	DBLP DOI BibTeX RDF	unique games, approximation algorithms, semidefinite programming, constraint satisfaction problems
11	Venkatesh Raman 0001, Saket Saurabh 0001, Somnath Sikdar	Improved Exact Exponential Algorithms for Vertex Bipartization and Other Problems.	ICTCS	2005	DBLP DOI BibTeX RDF
11	Ankur Bhargava, S. Rao Kosaraju	Derandomization of Dimensionality Reduction and SDP Based Algorithms.	WADS	2005	DBLP DOI BibTeX RDF
11	Jinhui Yuan, Bo Zhang 0010, Fuzong Lin	Graph Partition Model for Robust Temporal Data Segmentation.	PAKDD	2005	DBLP DOI BibTeX RDF
11	Jin Hyeong Park, Hongyuan Zha, Rangachar Kasturi	Spectral Clustering for Robust Motion Segmentation.	ECCV (4)	2004	DBLP DOI BibTeX RDF
11	Viera Sipková	Efficient Variable Allocation to Dual Memory Banks of DSPs.	SCOPES	2003	DBLP DOI BibTeX RDF