NDLI: Hill-climbing finds random planted bisections

Please wait, while we are loading the content...

Combinatorial approximation algorithms for the maximum directed cut problem

Approximation algorithms for the 0-extension problem

A faster implementation of the Goemans-Williamson clustering algorithm

Tree packing and approximating k-cuts

Generating well-shaped Delaunay meshed in 3D

Approximation algorithms for TSP with neighborhoods in the plane

Dynamic skin triangulation

Online point location in planar arrangements and its applications

Reconciling simplicity and realism in parallel disk models

Distribution sort with randomized cycle

External memory BFS on undirected graphs with bounded degree

I/O-efficient algorithms for graphs of bounded treewidth

Constructing worst case instances for semidefinite programming based approximation algorithms

Randomizing combinatorial algorithms for linear programming when the dimension is moderately high

Approximation algorithms for the metric labeling problem via a new linear programming formulation

Lattice approximation and linear discrepency of totally unimodular matrices

On polynomial approximation to the shortest lattice vector length

Approximation for minimum triangulation of convex polyhedra

Optimal covering tours with turn costs

Maintaining approximate extent measures of moving points

Simplified kinetic connectivity for rectangles and hypercubes

Static and kinetic geometric spanners with applications

Gossip is synteny: incomplete gossip and an exact algorithm for syntenic distance

Absolute convergence: true trees from short sequences

Performance study of phylogenetic methods: (unweighted) quartet methods and neighbor-joining

A probabilistic analysis of a greedy algorithm arising from computational biology

On the midpath tree conjuncture: a counter-example

Distance labeling in graphs

Steiner points in tree metrics don't (really) help

Fast approximation of centrality

K-pair delay constrained minimum cost routing in undirected networks

A deterministic algorithm for the cost-distance problem

Shape sensitive geometric permutations

Geometric permutations of high dimensional spheres

Inserting an edge into a planar graph

Entropy-preserving cuttings and space-efficient planar point location

A simple entropy-based algorithm for planar point location

An experimental study of an opportunistic index

Overlap matching

A linear lower bound on index size for text retrieval

Pattern matching for sets of segments

Approximate subset matching with Don't Cares

Dynamic string searching

On approximating the achromatic number

Coloring k-colorable graphs using smaller palettes

Approximating coloring and maximum independent sets in 3-uniform hypergraphs

Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction

Computing optimal α-fat and α-small decompositions

Optimal planar point location

Polygonal path approximation with angle constraints

Reconstructing a collection of curves with corners and endpoints

Web caching using access statistics

Competitive on-line stream merging algorithms for media-on-demand

On-line restricted caching

Approximate majorization and fair online load balancing

Game theory, algorithms, and the Internet

Learning Markov networks: maximum bounded tree-width graphs

Approximately covering by cycles in planar graphs

Practical approximation algorithms for zero- and bounded-skew trees

Approximating the minimum strongly connected subgraph via a matching lower bound

Improved approximation algorithms for rectangle tiling and packing

Secure notarization of paper text documents

Sublinear time approximate clustering

Efficient oblivious transfer protocols

Constructing pseudo-random permutations with a prescribed structure

Robust algorithms for restricted domains

Polynomial algorithms for partitioning problems on graphs with fixed clique-width (extended abstract)

A polynomial time recognition algorithm for probe interval graphs

Colored Tutte polynomials and Kaufman brackets for graphs of bounded tree width

A new constructive root bound for algebraic expressions

Orderly spanning trees with applications to graph encoding and graph drawing

Alternatives to splay trees with O(log n) worst-case access times

Worst case constant time priority queue

Representing dynamic binary trees succinctly

Making data structures confluently persistent

Compact labeling schemes for ancestor queries

Better approximation algorithms for bin covering

New approaches to covering and packing problems

Parallel processor scheduling with delay constraints

Approximation algorithms for extensible bin packing

Scheduling precedence-constrained jobs with stochastic processing times on parallel machines

Loss-bounded analysis for differentiated services

Stability preserving transformations: packet routing networks with edge capacities and speeds

Distributed admission control, scheduling, and routing with stale information

On algorithms for efficient data migration

Fast distributed graph coloring with O(Δ) colors

Improved algorithms for fault tolerant facility location

Algorithms for facility location problems with outliers

The probabilistic relationship between the assignment and asymmetric traveling salesman problems

Approximation algorithms for data placement in arbitrary networks

Polynomial-time approximation schemes for geometric graphs

Morphing between polylines

Fast implementation of depth contours using topological sweep

Computing the depth of a flat

Which formulae shrink under random restrictions?

Selective families, superimposed codes, and broadcasting on unknown radio networks

Adversarial models in evolutionary game dynamics

The phase transition in 1-in-k SAT and NAE 3-SAT

Guessing secrets

Can entropy characterize performance of online algorithms?

Competitive auctions and digital goods

Towards understanding the predictability of stock markets from the perspective of computational complexity

Performance guarantee for online deadline scheduling in the presence of overload

Assigning chain-like tasks to a chain-like network

The inverse nearest neighbor problem with astrophysical applications

Reductions among high dimensional proximity problems

A cell probe lower bound for dynamic nearest-neighbor searching

Shape matching using edit-distance: an implementation

On validating planar worlds

Improved fast integer sorting in linear space

Single-source shortest-paths on arbitrary directed graphs in linear average-case time

Optimal constrained graph exploration

An efficient algorithm for the configuration problem of dominance graphs

Linear reductions of maximum matching

Internet packet filter management and rectangle geometry

Faster kinetic heaps and their use in broadcast scheduling

Finding least common ancestors in directed acyclic graphs

On binary searching with non-uniform costs

Soft kinetic data structures

Testing graphs for colorable properties

Random lifts of graphs

Improved results for route planning in stochastic transportation

Hill-climbing finds random planted bisections

On universally easy classes for NP-complete problems

The diameter of random massive graphs

Domatic partitions and the Lovász local lemma

Equitable colorings extend Chernoff-Hoeffding bounds

Universal configurations in light-flipping games

On the discrete Bak-Sneppen model of self-organized criticality

Hill-climbing finds random planted bisections

Content Provider	ACM Digital Library
Author	Impagliazzo, Russell Carson, Ted
Abstract	We analyze the behavior of hill-climbing algorithms for the minimum bisection problem on instances drawn from the “planted bisection” random graph model, Gn,p,q, previously studied in [3, 4, 10, 11, 14, 9, 7]. This is one of the few problem distributions for which various popular heuristic methods, such as simulated annealing, have been proven to succeed. However, it has been open whether these sophisticated methods were necessary, or whether simpler heuristics would also work. Juels [14] made the first progress towards an answer by showing that simple hill-climbing does suffice for very wide separations between p and q.Here we give a more complete answer. A simple, polynomial-time, hill-climbing algorithm for this problem is given and shown to succeed in finding the planted bisection with high probability if p - q = &OHgr; $(n^{-½}ln^{3}n).$ For dense graphs, this matches the condition for optimality of the planted bisection to within a polylogarithmic factor. Furthermore, we show that a generic randomized hill-climbing algorithm succeeds in finding the planted bisection in polynomial time if p - q = &OHgr; $(n^{-¼}$ $ln^{3}$ n), for any ∈ > 0. This algorithm, studied also by [14], is a degenerate case of both Metropolis and go-with-the-winners, and the range here properly includes those analyzed in [11, 9, 14]. So this result implies, extends, and unifies those from [11, 9, 14]. Thus, to get a provable distinction between simulated annealing and hill-climbing for natural problems will require considerable progress both on new positive results for SA and new negative results for hill-climbing methods.
Starting Page	903
Ending Page	909
Page Count	7
File Format	PDF
ISBN	0898714907
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2001-01-09
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in