NDLI: Robust algorithms for restricted domains

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

Robust algorithms for restricted domains

Content Provider	ACM Digital Library
Author	Raghavan, Vijay Spinrad, Jeremy
Abstract	We introduce a new definition of efficient algorithms for restricted domains. Under this definition, an algorithm is required to be “robust,” i.e., it must produce correct output regardless of whether the input actually belongs to the restricted domain or not. This is to be contrasted with the “promise” version of solving problems on restricted domains, in which there is a guarantee that the input is in the class, and an algorithm to “solve” the problem need not function correctly or even terminate if this guarantee is not met.The more stringent requirement of robustness in algorithms gives an important benefit: such algorithms are amenable to manipulation as building blocks of more general algorithms; in other words, composition of robust algorithms preserves robustness. In contrast, promise algorithms cannot be so composed.There exist problems which have a polynomial time promise solution, while being NP-hard if required to be robust. We show the perhaps surprising result that finding a maximum independent set in a well-covered graph (i.e., a graph in which every maximal independent set is of the same size) is NP-hard. An argument can be made that this hardness result is more meaningful than the trivial polynomial time promise algorithm.Graph classes provide interesting natural restricted domains; there are many problems which are efficiently solvable given a special and natural representation of a graph (i.e., a “model”), but which are open with respect to time complexity if the graph is given in a general form such as an adjacency list or an adjacency matrix. One such open problem is that of finding a maximum clique in unit disk graphs here, we give a polynomial time robust algorithm for this problem, i.e., given an input graph G in general form, the output is either a maximum clique for G or a certificate that G is not a unit disk graph. The existence of this algorithm is to be reconciled with the apparent contradiction posed by the facts:Recognizing whether an input graph given in general form is a unit disk graph is NP-hard; in fact, it is not even known to be in NP.Finding a maximum clique in an input graph given in general form is NP-hard.
Starting Page	460
Ending Page	467
Page Count	8
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