Sergey
V. Sevastianov - Major Publications
Last
Updated:
10/27/04
N. Alon, Y. Azar, J. Csirik, L.
Epstein, S.V. Sevastianov, A.P.A. Vestjens, and G. Woeginger,
On-line and off-line
approximation algorithms for vector covering problems,
Fourth European Symposium on Algorithms (Barcelona, 1996),
Algorithmica, 21 (1998), no. 1, 73-79.
S.V. Sevast'yanov, Seven problems: so different yet close, in: R.Burkard and G.Woeginger (Eds.),
Algorithms --- ESA'97, 5th Annual European Symposium, Graz,
Austria, September 1997. Proceedings,
Lecture Notes in
Comp.Sci., 1284, Springer-Verlag, 1997,
443-458.
S.V. Sevast'janov and W.
Banaszczyk, To
the Steinitz lemma in coordinate form,
Discrete
Math., 169 (1997), 145-152.
S.V. Sevastianov,
Nonstrict vector summation in the plane
and its application to scheduling
problems,
in: A.D. Korshunov (ed.), Operations Research and Discrete
Analysis, Kluwer, Dordrecht, 1997, 241-272.
N. Alon, J. Csirik,
S. Sevastianov, A. Vestjens, and G. Woeginger,
On-line and off-line algorithms for
vector covering, Proc. ESA'96,
Lecture Notes in Comp.Sci., 1136,
Springer-Verlag, 1996, 406-418.
S.V. Avgustinovich and S.V.
Sevast'janov, Vector summation within minimal angle,
Computational
Geometry: Theory and Appl. 2 (1993),
235-239.
S.V. Sevastianov,
On a compact vector summation,
(in Russian),
Diskretnaya Matematika, 3
(1991), no. 3, 66-72.
S.V. Sevastianov, Theorem on a compact vector summation in
two-dimensional space, (in Russian),
Metody Diskret. Analiz.,
47 (1988), 61-65.
S.V. Sevastianov, Estimates and properties of Steinitz
functions, (in Russian),
Metody Diskret. Analiz., 36
(1981), 59-73.
S.V. Sevastianov, On the connection between the
calendar-planning problem and a problem
on the unit cube, (in
Russian), Metody Diskret. Analiz., 35
(1980), 93-103.
V.S. Grinberg and
S.V. Sevast'janov, Value of
the Steinitz constant,
Functional Anal. Appl., 14
(1980), 125-126.
S.V. Sevastianov,
On the problem of
compact summation of vectors, (in Russian),
Metody Diskret.
Analiz., 33 (1979), 77-89.
S.V. Sevastianov and A.V. Kononov, On the complexity of
the connected list vertex-coloring problem,
(in Russian), Diskret. Analiz i Issled. Oper., Ser. 1, 7
(2000), no. 2, 21-46.
S.V. Sevastianov,
Interval
colorability of the edges of a bipartite graph, (in Russian),
Metody
Diskret. Analiz., 50 (1990), 61-72.
 complexity theory |
 List
of topics |
S.V. Sevastianov,
Introduction to multi-parameter
complexity analysis of discrete problems,
European J. Oper. Res. 165 (2005), no. 2,
387-397.
A.A. Ageev, A.V. Fishkin, A.V. Kononov, and S.V. Sevastianov, Open block scheduling
in
optical communication networks, Theoretical Comp. Sci.,
submitted.
Ph. Baptiste, J. Carlier, A. Kononov,
M. Queyranne, S.V. Sevastianov, and M. Sviridenko,
Structural properties of preemptive schedules,
J. of Scheduling, submitted.
A.A. Ageev, A.V. Fishkin, A.V.
Kononov, and S.V. Sevastianov, Open block scheduling in optical
communication networks, in:
"Approximation and online algorithms: first International workshop
(WAOA 2003)''; Budapest, Hungary, September 16-18, 2003.
Lecture Notes in Comp.
Sci.,
2909, Springer-Verlag,
2004, 13-26.
S.V. Sevastianov,
Geometrical heuristics for
multiprocessor flow shop scheduling with uniform
machines at each stage, J. Scheduling, 5 (2002),
205-225.
S.V. Sevastianov and G.J. Woeginger,
Linear time approximation scheme for the
multiprocessor
open shop problem, Discrete Appl. Math., 114 (2001),
273-288.
K.N. Kashyrskikh, K.N. Potts, and
S.V. Sevastianov, 3/2-Approximation algorithm for two-machine
flow-shop sequencing subject to release dates, Discrete Appl.
Math.,
114 (2001), 255-271.
K.N. Kashyrskikh, A.V. Kononov, S.V.
Sevastianov, and I.D. Tchernykh,
Polynomial time solvable
case of the 2-stage 3-machine open shop problem, (in Russian), Diskret.
Analiz i Issled. Oper., Ser. 1,
8 (2001), no. 1, 23-39.
K.N. Kashyrskikh, S.V. Sevastianov, and I.D. Tchernykh,
Four-parameter complexity analysis of
the
open shop problem, (in Russian), Diskret. Analiz i Issled. Oper.,
Ser. 1,
7 (2000), no. 4, 59-77.
E.Kh. Gimadi, S.V. Sevastianov, and V.V. Zaljubovsky,
Polynomial solvability of the project
scheduling problem with accumulative resources and deadlines, (in
Russian),
Diskret. Analiz i Issled. Oper., Ser. 2, 7 (2000), no.
1, 9-34.
G.J. Woeginger and S.V. Sevastianov,
Linear time approximation scheme for the multiprocessor
open shop problem, (in Russian), Diskret. Analiz i Issled. Oper.,
Ser. 1,
6 (1999), no. 2, 3-22.
A. Kononov, S. Sevastianov, and
I. Tchernykh, When
difference in machine loads leads to efficient
scheduling in open
shops, Annals Oper.Res., 92 (1999), 211-239.
S.V. Sevastianov,
Nonstrict
vector summation in multi-operation scheduling,
Annals Oper.Res., 83 (1998), 179-211.
S.V. Sevastianov and I.D.
Tchernykh, Computer-aided
way to prove theorems in scheduling,
Bilardi, a.o. (Eds.), Algorithms -- ESA'98,
6th Annual European Symposium, Venice, Italy,
August 1998.
Proceedings,
Lecture Notes in Comp.Sci., 1461,
Springer-Verlag, 1998, 502-513.
Sergey V. Sevastianov, Gerhard
J. Woeginger, Makespan minimization in preemptive two machine
job
shops, Computing, 60 (1998),
no.1, 73-79.
S.Sevastianov and G.Woeginger, Makespan minimization in open shops: a
polynomial time
approximation scheme, Math. Programming,
82 (1998), 191-198.
S.V. Sevast'yanov, Nonstrict vector
summation in the plane and its application to scheduling
problems,
in: A.D.Korshunov (ed.), Operations Research and
Discrete Analysis, Dordrecht, Kluwer, 1997, 241-272.
D.P.Williamson, L.A.Hall,
J.A.Hoogeveen, C.A.J.Hurkens, J.K.Lenstra, S.V.Sevastianov, and
D.B.Shmoys,
Short shop schedules, Oper.Res., 45
(1997), no.2,
288-294.
K.N. Kashyrskikh, C.N. Potts,
and S.V. Sevastianov,
Improved algorithm for two-machine flow-shop
sequencing subject
to release dates, (in Russian), Diskret. Analiz i Issled. Oper., 4
(1997), no. 1, 13-32.
S.V.Sevastianov and
G.J.Woeginger, Makespan minimization in preemptive two
machine job shops,
SFB-Report
81, July 1996, TU Graz, Austria.
S.V.Sevastianov and
G.J.Woeginger, Makespan minimization in open shops: a
polynomial time
approximation, SFB-Report 68, Mai 1996, TU Graz, Austria.
S.V. Sevast'yanov, Nonstrict vector
summation in scheduling problems, in: A.D.Korshunov (ed.),
Discrete Analysis and Oper. Res., Dordrecht, Kluwer, 1996,
257-287.
S.V. Sevast'yanov, Efficient
scheduling in open shops, in: A.D.Korshunov (ed.), Discrete
Analysis
and Oper. Res., Dordrecht, Kluwer, 1996, 235-255.
S.V. Sevastianov and I.D.
Chernykh, A
sufficient condition for the open shop problem to be
solvable
in polynomial time, (in Russian), Diskret. Analiz i
Issled. Oper., 3 (1996), No.1, 57-74.
S.V. Sevastianov,
Nonstrict vector summation in
multi-operation scheduling,
Memorandum COSOR 95-37, Eindhoven University
of Technology, 1995, 40 p.
C.N. Potts, S.V. Sevast'janov,
V.A. Strusevich, L.N.Van Wassenhove, and C.M. Zvaneveld,
The two-stage
assembly scheduling problem: complexity and approximation, Oper.
Res., 43 (1995), no. 2, 346-355.
S.V. Sevast'janov, Vector summation in Banach space and
polynomial algorithms for
flow shops and open shops, Math. Oper. Res.
20 (1995), 90-103.
S.V. Sevast'janov, On Some Geometric
Methods in Scheduling Theory: a survey,
Discrete Appl. Math.
55 (1994), 59-82.
Ju.D. Neumytov and S.V.
Sevastianov, Approximation
algorithm with tight bound for three-machine
counter-routes
problem, (in Russian), Upravlyaemye Sistemy, 31
(1993), 53-65.
S.V. Sevastianov, Construction of a near-optimal schedule
for a flow-type system, (in Russian),
Upravlyaemye Sistemy,
31 (1993), 66-71.
C.N. Potts, S.V. Sevast'janov,
V.A. Strusevich, L.N. Van Wassenhove, and C.M. Zvaneveld,
The two-stage assembly scheduling
problem: complexity and approximation, Report 9256/A,
Erasmus
University Rotterdam, The Netherlands, 1992.
S.V. Sevast'janov, Polynomially solvable case of the open-shop
problem with arbitrary number
of machines, Cybernet.
Systems Anal., 28 (1992), no. 6, 918-933
(1993), (translated from Russian).
S.V.Sevastianov, Geometry in scheduling theory, (in
Russian),
Models and methods of optimization, Trudy Inst.
Mat., 10, Novosibirsk, "Nauka",
1988, 226-261.
S.V. Sevast'janov, An algorithm with an estimate for a problem
with routings of parts of
arbitrary shape and alternative executors, Cybernetics, 22
(1986),
773-781.
S.V. Sevast'yanov, Efficient construction of schedules
close to optimal for the class of arbitrary
and alternative
routes of parts, Soviet Math. Dokl., 29 (1984),
447-450.
S.V. Sevastianov, Algorithms with estimates for the
Johnson and the Akers-Friedman problems
in the case of three machines, (in Russian), Upravlyaemye Sistemy,
22
(1982), 51-57.
S.V. Sevastianov, Algorithms with performance guarantees
for scheduling problems, (in Russian),
Ph.D. Thesis,
Novosibirsk (1981).
S.V. Sevastianov, Some generalizations of the Johnson
problem, (in Russian),
Upravlyaemye Sistemy, 21
(1981), 45-61.
S.V. Sevastianov, Approximate solution to a calendar-planning
problem, (in Russian),
Upravlyaemye
Sistemy, 20 (1980), 49-63.
S.V. Sevastianov, Approximation algorithms for Johnson's
and vector summation problems,
(in Russian), Upravlyaemye
Sistemy, 20 (1980), 64-73.
S.V. Sevastianov, Approximate solution of some problems of
scheduling theory, (in Russian),
Metody Diskret. Analiz.,
32 (1978), 66-75.
S.V. Sevastianov, Asymptotical approach to some scheduling
problems, (in Russian),
Upravlyaemye Sistemy, 14
(1975), 40-51.
S.V. Sevastianov, Asymptotical approach to some scheduling
problems, (in Russian), in:
Third All-Union Conf. Problems of
Theoretical Cybernetics. Thes. Dokl., Novosibirsk (June,
1974), 67-69.
A.I. Erzin and S.V.
Sevastianov, Algorithms of
solving the mines productivity scheduling problem
while mining
minerals of nonhomogeneous quality, (in Russian),
Fiziko-tech.
problemy razrabotki polez. iskopaemykh (1989), no. 5, 35-42.
S.V. Sevastianov and A.I.
Erzin, Algorithms of
solving the mines productivity scheduling problem
while mining
several technological kinds of minerals, (in Russian),
Fiziko-tech.
problemy razrabotki polez. iskopaemykh (1985), no. 5, 80-88.
E.Kh. Gimadi, N.M. Puzynina,
and S.V. Sevastianov, On
some extremal problems of realization of
large-scale BAM-type
projects, (in Russian), Ekonomika i Mat. Metody, (1979), no.
5, 1017-1020.
S.V. Sevastianov, Optimization of the servicing and the
construction of linear objects, (in Russian),
Upravlyaemye
Sistemy, 17 (1978), 67-75.
V.A. Perepelica and S.V.
Sevastianov, A scheduling
problem on a network, (in Russian),
Upravlyaemye Sistemy,
15 (1976), 48-67.
