Index Catalog // Carleton University Institutional Repository

Start Over

Filtering by: Creator Krizanc, Danny Creator Kirousis, Lefteris M.

Station layouts in the presence of location constraints

Resource Type:

Conference Proceeding

Creator:

Peleg, David, Krizanc, Danny, Kirousis, Lefteris M., Kranakis, Evangelos, Kaklamanis, Christos, and Bose, Prosenjit

Abstract:

In wireless communication, the signal of a typical broadcast station is transmited from a broadcast center p and reaches objects at a distance, say, R from it. In addition there is a radius r, r < R, such that the signal originating from the center of the station is so strong that human habitation within distance r from the center p should be avoided. Thus every station determines a region which is an “annulus of permissible habitation". We consider the following station layout (SL) problem: Cover a given (say, rectangular) planar region which includes a collection of orthogonal buildings with a minimum number of stations so that every point in the region is within the reach of a station, while at the same time no building is within the dangerous range of a station. We give algorithms for computing such station layouts in both the one-and two-dimensional cases.

Date Created:

1999-01-01
Approximating the unsatisfiability threshold of random formulas: (Extended abstract)

Resource Type:

Conference Proceeding

Creator:

Krizanc, Danny, Kranakis, Evangelos, and Kirousis, Lefteris M.

Abstract:

Let φ be a random Boolean formula that is an instance of 3-SAT. We consider the problem of computing the least real number such that if the ratio of the number of clauses over the number of variables of φ strictly exceeds κ, then φ is almost certainly unsatisfiable. By a well known and more or less straightforward argument, it can be shown that κ 3.

Date Created:

1996-01-01

Station layouts in the presence of location constraints

Approximating the unsatisfiability threshold of random formulas: (Extended abstract)

Limit your search

Collection

Resource Type

Date Created

Creator

Language

Search Constraints

Search Results

Station layouts in the presence of location constraints

Approximating the unsatisfiability threshold of random formulas: (Extended abstract)

Limit your search

Collection

Resource Type

Date Created

Creator

Language